LeetCode 877 Stone Game

Tag: 动态规划问题 LeetCode Posted on 2022-02-20 09:46:02 Edited on 2022-03-01 11:33:37 Views: 176

概述

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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/