LeetCode 877 Stone Game

    
        标签：
        
            动态规划问题
        
            LeetCode
        
    发布于：2022-02-20 09:46:02
    编辑于：2022-03-01 11:33:37
    浏览量：850

概述

https://leetcode.com/problems/stone-game/

贪心法

贪心可以吗？每次只拿最大的？貌似不太行的样子，因为可能会将更大的石头暴露出来。

动态规划法

dp 数组的定义：dp[i][j] = (先手分数，后手分数)

i 和 j 为剩余石头的端点。

class Solution {
public:
    vector<vector<array<int, 2>>> dp;
    bool stoneGame(vector<int>& piles) {
        dp.resize(piles.size(), vector<array<int, 2>>(piles.size(), {-1, -1}));
        return helper(piles, 0, piles.size() - 1, 0) > helper(piles, 0, piles.size() - 1, 1);
    }
    
    int helper(vector<int>& piles, int i, int j, int h) {
        if (i == j) {
            if (h == 0) return piles[i];
            else return 0;
        }
        if (dp[i][j][h] != -1) return dp[i][j][h];
        int chooseLeft = piles[i] + helper(piles, i + 1, j, 1);
        int chooseRight = piles[j] + helper(piles, i, j - 1, 1);
        if (chooseLeft >= chooseRight) {
            dp[i][j][0] = chooseLeft;
            dp[i][j][1] = helper(piles, i + 1, j, 0);
        } else {
            dp[i][j][0] = chooseRight;
            dp[i][j][1] = helper(piles, i, j - 1, 0);           
        }
        return dp[i][j][h];
    }
};

这道题比较有意思的地方是，先手后手是同步算出来的。

分析法

https://labuladong.gitee.io/algo/4/30/124/#二石头游戏

偶数堆个石头，总数为奇数，那么以索引的奇偶划分石头堆，必然数目不同。

又因为你是先手，所以可以选择拿全部的偶数堆或全部的奇数堆，所以先手必胜。

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        return true;
    }
};

Links: leetcode-877-stone-game