有一个长度为n的数列arr, 甲乙两个人每次可以从头或者从末尾取一个数,双方都想让自己取数之和尽量多,
甲先取数,问甲乙在采取最优策略的基础下,甲最多得多少分?
n<=800
示例
给定arr=[8,6,9,4,4,3],返回21
给定arr=[1,3,5,8,7,9,1],返回14
相关题目:LeetCode 博弈DP系列
dp[i][j]
表示 剩下的数字的区间为 [i,j]
时,先手的最大分差,使用区间DP求取class Solution {
public:
/**
* @param arr: the number array
* @return: output the maximal score Alice can get
*/
int getAns(vector<int> &arr) {
// Write your code here
int n = arr.size();
int sum = accumulate(arr.begin(), arr.end(), 0);//总的分数
vector<vector<int>> dp(n, vector<int>(n, 0));
for(int i = 0; i < n; i++)
dp[i][i] = arr[i];//只剩一个数字时的得分
for(int len = 1; len <= n; len++)
{
for(int i = 0; i+len < n; i++)
{
int j = i+len;
dp[i][j] = max(-dp[i+1][j]+arr[i], -dp[i][j-1]+arr[j]);
// 上一个人的分差取负就是我的分差,加上我的得分,两种选择取大的
}
}
return (sum+dp[0][n-1])/2;
}
};
50ms C++