3ms Simplest DP formula solution


  • 0

    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;
        }
    };
    

Log in to reply
 

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