lintcode395. 硬币排成线 II动态规划

╰半橙微兮° 2023-07-05 10:27 2阅读 0赞

有 n 个不同价值的硬币排成一条线。两个参赛者轮流从 左边 依次拿走 1 或 2 个硬币，直到没有硬币为止。计算两个人分别拿到的硬币总价值，价值高的人获胜。  
请判定 先手玩家 必胜还是必败?  
若必胜, 返回 true, 否则返回 false.

样例
    样例 1:
    
    输入: [1, 2, 2]
    输出: true
    解释: 先手玩家直接拿走两颗硬币即可.
    样例 2:
    
    输入: [1, 2, 4]
    输出: false
    解释: 无论先手拿一个还是两个, 后手可以拿完, 然后总价值更高.

思路：  
从后面往前计数，dp\[0\]就是可以的得到的最高价值。  
而先手者只有可能最后拿到倒数第一，第二，第三个硬币，所以有：  
dp\[len-1\]=values\[len-1\]  
dp\[len-2\]=values\[len-2\]+values\[len-1\]  
dp\[len-3\]=values\[len-3\]+values\[len-2\]，在有可能多取的时候尽量多取。  
当i = len-4以及以后的情况中，显然可以选择拿一个或者拿两个两种情况，我们自然是选择拿最多的那个作为dp的值，那么我们就分分析这两种情况：  
第一种，只拿一个,那么对手可能拿两个或者一个，对手肯定是尽可能多拿，所以我们要选择尽可能小的那个，所以dp\[i\] = values\[i\] + min(dp\[i+2\],dp\[i+3\])  
第二种，拿两个，同样的情况，dp\[i\] = values\[i\]+ values\[i+1\]+min(dp\[i+3\],dp\[i+4\])  
所以，最后，我们要在这两种情况中，取较大的一个，因为我们可以选择较大的一种情况走，而因无法决定对手的情况，对手肯定多拿，所以前面的情况只能选小的那个

class Solution {
        
    public:
        /**
         * @param values: a vector of integers
         * @return: a boolean which equals to true if the first player will win
         */
        bool firstWillWin(vector<int> &values) {
        
            // write your code here
            int len=values.size();
            if(len<=2) return true;
            vector<int> dp(len+1,0);
            dp[len]=0;
            dp[len-1]=values[len-1];
            dp[len-2]=values[len-2]+values[len-1];
            dp[len-3]=values[len-2]+values[len-3];
            int sum=values[len-1]+values[len-2]+values[len-3];
            for (int i = len-4; i >= 0 ; i--) {
        
                /* code */
                sum+=values[i];
                dp[i]=max(values[i]+min(dp[i+2],dp[i+3]),values[i]+values[i+1]+min(dp[i+3],dp[i+4]));
            }
            return dp[0]>sum-dp[0];
        }
    };