leetcode 486.Predict the Winner
Opened this issue · 0 comments
maninbule commented
状态表示:dp[i][j] = {first,second}
表示区间[i,j]中,前者最高得first分数,后者最高得second分
状态转移:dp[i][j].first = max(nums[i]+dp[i+1][j].second,nums[j]+dp[i][j-1].second)
dp[i][j].second选对应的first,dp[i+1][j].first or dp[i][j-1].first
状态初始值:dp[i][i] = {nums[i],0}
为什么是nums[i]+dp[i+1][j].second?
因为当前者选了nums[i]
,后者肯定是dp[i+1][j].first
所以 前者:nums[i]+dp[i+1][j].second
,后者:nums[i]+dp[i+1][j].first
我参考的题解视频:https://www.youtube.com/watch?v=WxpIHvsu1RI
typedef pair<int,int> pii;
class Solution {
public:
//pair<int,int> dp[1010][1010];
bool PredictTheWinner(vector<int>& nums) {
vector<vector<pii>> dp(nums.size(), vector<pii>(nums.size())); // 定义一个pair<int,int>类型的二维数组
int len = nums.size();
for(int i = 0;i<len;i++) dp[i][i] = {nums[i],0};
for(int k = 1;k<len;k++){
for(int i = 0;i+k<len;i++){
int j = i+k;
int sum1 = nums[i]+dp[i+1][j].second,sum2 = nums[j]+dp[i][j-1].second;
if(sum1 >= sum2) dp[i][j] = {sum1,dp[i+1][j].first};
else dp[i][j] = {sum2,dp[i][j-1].first};
}
}
return dp[0][len-1].first >= dp[0][len-1].second;
}
};
另一种改写的方式,把pair{first,second}
改成了first-second
状态转移方程dp[i][j] = max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])
,
dp[i][j]
为正前者大为负后者大, 其实和上面的代码差不多
typedef pair<int,int> pii;
class Solution {
public:
bool PredictTheWinner(vector<int>& nums) {
vector<vector<int>> dp(nums.size(), vector<int>(nums.size()));
int len = nums.size();
for(int i = 0;i<len;i++) dp[i][i] = nums[i];
for(int k = 1;k<len;k++){
for(int i = 0;i+k<len;i++){
int j = i+k;
dp[i][j] = max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1]);
}
}
return dp[0][len-1]>=0;
}
};