面值为正数的硬币放置成一排，玩家1和玩家2轮流拿走硬币，规定每个玩家在拿硬币时，只能拿走最左或最右的硬币。 例如： 硬币面值与排列为：1,2,3,4,5，现在轮到玩家1拿硬币。 在当前状态下，玩家1只能拿走1或5， 如果玩家1拿走1，则排列变为2,3,4,5，那么接下来玩家2可以拿走2或5，然后继续轮到玩家1拿硬币… 如果玩家1拿走5，则排列变为1,2,3,4，那么接下来玩家2可以拿走1或4；然后继续轮到玩家1拿硬币… 游戏按照这个规则进行，直到所有的硬币被拿完，每个玩家获得的分数是各自拿走硬币的总和。 游戏胜负的规定： 如果玩家1最后获得的分数大于玩家2，则玩家1获胜； 如果玩家2最后获得的分数大于玩家1，则玩家2获胜； 因为玩家1先拿硬币，所以如果最后两人获得分数一样则玩家2获胜； 给定一个数组arr，，表示硬币的面值和排列状况，请返回最终获胜者的分数。 例子： arr=[8,7,5,3] 玩家1将获胜，分数为13 所以返回13 arr=[1,9,1] 玩家2将获胜，分数为9 所以返回9
class Solution {public:int memorized_dfs(int i, int j, vector<vector<int> > &dp, vector<int> &A) {if (i == j)return dp[i][j] = A[i];else if (i > j)return 0;int v = max(min(A[i] + memorized_dfs(i + 2, j, dp, A),/* 先手拿左边, 后手拿剩下的左边 */A[i] + memorized_dfs(i + 1, j – 1, dp, A)),/* 先手拿左边, 后手拿剩下的右边 */min(A[j] + memorized_dfs(i + 1, j – 1, dp, A),/* 先手拿右边, 后手拿剩下的左边 */A[j] + memorized_dfs(i, j – 2, dp, A)));/* 先手拿右边, 后手拿剩下的右边 */return dp[i][j] = v;}/*** 得到硬币博弈问题的获胜分值* 输入：代表硬币排列情况的数组arr* 返回：硬币博弈问题的获胜分值*/int getWinValue(vector<int> arr, int len) {vector<vector<int> > dp(len, vector<int>(len, -1));int sum = 0;for (int i = 0; i < arr.size(); ++i)sum += arr[i];int first = memorized_dfs(0, len – 1, dp, arr);int second = sum – first;return max(first, second);}};
本题中dp数组应该不是必须的吧？
好像有头大象在吸水。然后再去了芦笛岩，
