486. Predict the Winner

jubincn 发布于2019-08-14 17:26 / 944人阅读

486. Predict the Winner

题目链接：https://leetcode.com/problems...

看了discussion里面参考的mit算法视频：https://www.youtube.com/watch...

recursion + memo 或者 iteration用dp table

public class Solution {
    public boolean PredictTheWinner(int[] nums) {
        // // even, always win
        // if(nums.length % 2 == 0) return true;
        
        int n = nums.length;
        // maximum score play1 can get
        int[][] dp = new int[n][n];
        int sum = 0;
        // base cases
        for(int i = 0; i < n; i++) {
            dp[i][i] = nums[i];
            sum += nums[i];
        }
        for(int i = 1; i < n; i++) dp[i-1][i] = Math.max(nums[i-1], nums[i]);
        
        // dp recur
        for(int i = n - 1; i >= 0; i--) {
            for(int j = i + 2; j = sum - dp[0][n-1];
    }
}

海外云主机私有云 Winner Predict the sdp for the webrtc

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66641.html

leetcode486. Predict the Winner

摘要：但是，往往会有可以优化的空间。假设我们用来记录子数组之间，第一个取数字的玩家和第二个取数字的玩家之间最大的差距。再考虑初始情况，即当数组长度为时，可以得知此时玩家一和玩家二之间的差距即为该数组元素的值。题目要求 Given an array of scores that are non-negative integers. Player 1 picks one of the numb...

王军 2019-08-19 10:25 评论0 收藏0
Leetcode 相似题只有题号不含代码。

找出string里的单词。 186. Reverse Words in a String II, 434. Number of Segments in a String combination类型题 77. Combinations 39. Combination Sum 40. Combination Sum II 216. Combination Sum III 494. Target S...

StonePanda 2019-08-14 18:01 评论0 收藏0
python设计模式-状态模式

摘要：很明显，有有分钱没有分钱售出糖果糖果售罄四个状态，同时也对应四个动作投入分钱，退回分钱，转动曲柄和发放糖果。状态模式的类图如下状态模式是将多个行为封装在状态对象中，的行为随时可委托到其中一个状态中。问题：有一个糖果公司需要设计一个糖果售卖机，控制流程如下图，需要怎么实现？ showImg(http://media.gusibi.mobi/5aI8Zy9kkfNI8jzRA8VYMG...

A Loity 2019-07-30 18:42 评论0 收藏0