dynamic programming

• Classification1

• One-dimensional DP problems

• Two-dimensional DP problems

  • Illustration of dp[i][j]

    i, j represent different object A and object B.
    The value of dp[i][j] represents the cost when A[i] and B[j].

  • Equations:

    • when the value doesn’t change :
      dp[i][j] = dp[i-1][j-1]
    • when the value changes :
      dp[i][j] = dp[i-1][j] + A[i-1] or dp[i][j-1] + B[j-1]
  • LeetCode

712. Minimum ASCII Delete Sum for Two Strings

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int minimumDeleteSum(string s1, string s2) {
    int m = (int)s1.size();
    int n = (int)s2.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    dp[0][0] = 0;
    for(int j = 1; j <= n; j++)
        dp[0][j] = dp[0][j-1] + s2[j-1];
    for(int i = 1; i <= m; i++){
        dp[i][0] = dp[i-1][0] + s1[i-1];
        for(int j = 1; j <= n; j++){
            if(s1[i-1] == s2[j-1])
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = min(dp[i-1][j]+s1[i-1], dp[i][j-1]+s2[j-1]);
        }
    }

    return dp[m][n];
}

486. Predict the Winner

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

int (vector<int>& nums,  vector<vector<int>>& dp, int i, int j){
   if(i > j)
       return 0;
   if(dp[i][j] != -1)
       return dp[i][j];

   int left = nums[i] + min(judge(nums, dp, i+1, j-1), judge(nums, dp, i+2, j));
   int right = nums[j] + min(judge(nums, dp, i+1, j-1), judge(nums, dp, i, j-2));

   return max(left, right);
}

bool PredictTheWinner(vector<int>& nums) {
   int n = (int)nums.size();
   if(n % 2 == 0)
       return true;
   vector<vector<int>> dp(n, vector<int>(n, -1));
   int sum = accumulate(nums.begin(), nums.end(), 0);
   int player1 = judge(nums, dp, 0, n-1);

   return player1 >= (sum - player1)? true : false;
}

Now, let’s analyze LeetCode486 which is very interesting.
Assumption: the current arrange of the list is nums(i, j)
So, the player1 can choose nums[i] or nums[j]. The choice bases on the nums[i] or nums[j] and the left numbers.
Since we assume that the player2 is clever enough. If we want to win this game, we should prepare for the worst. That is player2 can get the maximum, so player1 can just get the minimum.
The equations in this situation are

• If player1 chooses nums[i],
  the minimum of the left(from nums[i+1] to nums[j]) is minimum between nums(i+2, j)(the player2 chooses nums[i+1]) and nums(i+1, j-1)(the player2 chooses nums[j]).

• In the same case, if player1 chooses nums[j], the minimum of the left(from nums[i] to nums[j-1]) is minimum between nums(i+1, j-1)(the player2 chooses nums[i+1]) and nums(i, j-2)(the player2 chooses nums[j-1]).

• Classification2

• Bottom-up method
  746. Min Cost Climbing Stairs
  

  1 2 3 4 5 6 7 8 9 10 11

  int minCostClimbingStairs(vector<int>& cost) { int n = (int)cost.size(); vector<int>dp(n, 0); dp[0] = cost[0]; dp[1] = cost[1]; for(int i = 2; i < n; i++){ dp[i] = min(dp[i-1], dp[i-2]) + cost[i]; } return dp[n-1] > dp[n-2] ? dp[n-2] : dp[n-1]; }

When we want to reach the stair i, we can reach stair i-1 or stair i-2 at first.

• Top-down method