取石头游戏

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

int stoneGameII(vector<int>& piles) {
    // 设dp[i][m]表示从piles[i..]、参数M=m时的得分（能拿的最大石头数）
    // 拿掉前x个后，对手得分dp[i+x][max(m,x)]，最小化对手得分即最大化自己得分，
    // dp[i][m]=max{ sufsum[i] - dp[i+x][max(m,x)] }，1<=x<=2m
    // 初始dp[N][]=0，dp[i][N]=sufsum[i]
    const int N = piles.size();
    vector<int> sufsum(N + 1, 0);
    for (int i = N - 1; i >= 0; i--) {
        sufsum[i] = sufsum[i+1] + piles[i];
    }
    vector<vector<int>> memo(N + 1, vector<int>(N + 1, -1));
    function<int(int,int)> dp = [&](int i, int m) {
        if (i == N) return 0;
        if (m == N) return sufsum[i];
        if (memo[i][m] != -1) return memo[i][m];

        for (int x = 1; x <= 2 * m && i + x <= N; x++) {
            int sub = dp(i + x, max(m, x));
            memo[i][m] = max(memo[i][m], sufsum[i] - sub);
        }
        return memo[i][m];
    };
    return dp(0, 1);
}

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

bool winnerSquareGame(int n) {
    // 每次移出平方数个石头
    // 设dp[i]表示i个石头时能否赢，dp[i]=any{ !dp[i-squreNum] }
    vector<bool> dp(n + 1); // dp[0]==false
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k * k <= i; k++) {
            if (!dp[i - k * k]) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}

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

int stoneGameV(vector<int>& stones) {
    // 设dp[i][j]表示stones[i..j]的最大得分
    // dp[i][j] = max{ left+dp[i..k] 若left=sum[i..k]更小, 
    //                 right+dp[k+1..j] 若right=sum[k+1..j]更小) }
    // k在[i,j-1]。初始dp[i][i]=0
    const int N = stones.size();
    vector<int> presum(N + 1);
    for (int i = 0; i < N; i++) {
        presum[i+1] = presum[i] + stones[i];
    }
    vector<vector<int>> memo(N + 1, vector<int>(N + 1, -1));

    function<int(int, int)> dp = [&](int lo, int hi) {
        if (lo == hi) return 0;
        if (memo[lo][hi] != -1) return memo[lo][hi];

        int ans = 0;
        for (int k = lo; k < hi; k++) {
            int left = presum[k+1] - presum[lo];
            int right = presum[hi+1] - presum[k+1];
            if (left <= right) {
                ans = max(ans, left + dp(lo, k));
            } 
            if (left >= right) {
                ans = max(ans, right + dp(k+1, hi));
            } 
        }
        return memo[lo][hi] = ans;
    };
    return dp(0, N-1);
}

每K堆石头合并成一堆

https://leetcode.com/problems/minimum-cost-to-merge-stones

int mergeStones(vector<int>& stones, int K) {
    const int INF = 1e7;
    const int N = stones.size();
    // 就像汽水瓶换汽水的问题
    if ((N - 1) % (K - 1) != 0) return -1;
    // 设dp[i][j][m]表示把stones[i..j]合成m堆
    // dp[i][j][m] = min{ dp[i][mid][1] + dp[mid+1][j][m-1] }, mid在[i..j-m+1]
    // 初始dp[i][i][1]=0，dp[i][i][>1]=INF
    // 已知可合并，dp[i][j][1]=dp[i][j][K]+sum[i..j]

    vector<int> presum(N + 1);
    for (int i = 0; i < N; i++) {
        presum[i+1] = presum[i] + stones[i];
    } // sum[i..j]=presum[j+1]-presum[i]
    vector<vector<vector<int>>> memo(N + 1, vector<vector<int>>(N + 1, vector<int>(N + 1, -1)));
    function<int(int, int, int)> dp = [&](int lo, int hi, int m) {
        if (lo == hi) return m == 1 ? 0 : INF;
        if (m == 1) return dp(lo, hi, K) + presum[hi+1] - presum[lo];
        if (memo[lo][hi][m] != -1) return memo[lo][hi][m];
        
        int ans = INF;
        for (int mid = lo; mid <= hi - m + 1; mid++) {
            ans = min(ans, dp(lo, mid, 1) + dp(mid + 1, hi, m - 1));
        }
        return memo[lo][hi][m] = ans;
    };
    return dp(0, N - 1, 1);
}