# 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

486. Predict the Winner

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

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

• Top-down method