# 3ms Simplest DP formula solution

• I tried two DP formula solutions,
First 1, explanation from MIC OCW

``````class Solution {
public:
bool PredictTheWinner(vector<int>& nums) {
int n = nums.size();
if (n % 2 == 0 || n == 1) {
return true;
}

vector<vector<int>> v(n, vector<int>(n, 0));
for (int i = n - 1; i >= 0; --i) {
for (int j = i; j < n; ++j) {
v[i][j] = i == j ? nums[i] :
i+1 == j ? max(nums[i], nums[i+1]) :
max(nums[i] + min(v[i+1][j-1], v[i+2][j]), nums[j] + min(v[i][j-2], v[i+1][j-1]));
}
}

return v[0][n-1] * 2 >= accumulate(nums.begin(), nums.end(), 0);
}
};
``````

Second solution: change the v[i][j] from storing "max total value that first player can get" to "max delta value of first player can get to second player can get"
so the dp formula change to : v(i, j) = max(nums[i] - v(i+1, j), nums[j] - v(i, j-1)). If we manage the for each directions, we can change it to a 1 dimension formula.

``````class Solution {
public:
bool PredictTheWinner(vector<int>& nums) {
int n = nums.size();
if (n % 2 == 0 || n == 1) {
return true;
}

vector<int> v(n);
for (int i = n - 1; i >= 0; --i) {
v[i] = nums[i];
for (int j = i + 1; j < n; ++j) {
v[j] = max(nums[i] - v[j], nums[j] - v[j-1]);
}
}

return v[n-1] >= 0;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.