leetcode 困难题 1406. Stone Game III 石子游戏 III

Problem: 1406. Stone Game III 石子游戏 III

两种方案的

方案1是记忆化深度优先搜索，方案2是动态规划

记忆化深度优先搜索，函数dfs返回两者分数的最大差值，也就是两者分数差值越大越好，一般来讲需要最大化Alice或者Bob的分数，最大化Alice分数的同时需要最小化Bob的分数，最大化Bob分数的同时需要最小化Alice的分数

所以求出分数sum以后，sum - dfs(stoneValue, i + 1)，dfs表示对手分数的最大值差值，加上负号-，也就是最大化当前player的分数最小化对手的分数

满足博弈论的最优化选择，使用了记忆化搜索

方案1 Code

class Solution { public: int n; unordered_map<int, int> ump; int dfs(vector<int>& stoneValue, int start) { if(start >= n) return 0; if(ump.count(start) != 0) return ump[start]; int sum = 0, r = min(start + 3, n), mx = INT_MIN, ret; for(int i = start; i < r; i++) { sum += stoneValue[i]; ret = sum - dfs(stoneValue, i + 1); mx = max(ret, mx); } ump[start] = mx; return mx; } string stoneGameIII(vector<int>& stoneValue) { n = stoneValue.size(); int ans = dfs(stoneValue, 0); if(ans > 0) return "Alice"; else if(ans==0) return "Tie"; else return "Bob"; } };

方案2，dp[i]表示从stoneValue[i]到stoneValue.back()两者分数的最大差值，不管谁先谁后，从后向前，初始化dp[n]=0, dp[n-1] = stoneValue.back();

然后递推公式是：dp[i] = max(dp[i], sum - dp[j+1]);，sum就是当前player拿到的分数，dp[j+1]是对手拿到的分数最大差值，两者的差值要最大化

方案2 Code

class Solution { public: int n; string stoneGameIII(vector<int>& stoneValue) { n = stoneValue.size(); vector<int> dp(n+1, INT_MIN); dp[n] = 0; dp[n-1] = stoneValue.back(); for(int i = n-2; i >= 0; i--) { int sum = 0, r = min(n, i + 3); for(int j = i; j < r; j++) { sum += stoneValue[j]; dp[i] = max(dp[i], sum - dp[j+1]); } } int ans = dp[0]; if(ans > 0) return "Alice"; else if(ans==0) return "Tie"; else return "Bob"; } };