First, applicable conditions

It has overlapping subproblems

Subproblems are not independent and may be used many times in subsequent calculations. Subproblems can also be divided into smaller subproblems in the same way.

Satisfies the optimal substructure

Once the state of a certain stage is determined, it will not be affected by the decision after this state, that is, the domestic production after a certain state will not affect the former state, only related to the current state.

There was no aftereffect

Decisions made on each subproblem cannot affect subsequent unresolved problems.

Two, three steps of dynamic programming

Step 1: Define the meaning of the array elements

In general, one-dimensional or two-dimensional arrays are used to store data. You need to specify what the array represents, for example, dp[I].

Step 2: Find the relationship between array elements (state transition equation)

When we want to calculate dp[n], we can use dp[n-1], dp[n-2]… For example, dp[n] = dp[n-1] + dp[n-2], which is the most difficult step and the most critical step.

Step 3: Find the initial value

The initial conditions are derived from the constraints.

Common dynamic programming problems

Case 1: Simple one-dimensional DP

Frog jumps step:

  1. Dp [I] = dp[I] = dp[I] = dp[I]
  2. State transition equation: DP [n] = DP [n-1] + DP [n-2]
  3. Initial conditions: DP [0] = 0, DP [1] = 1, DP [2] = 2
int f(int n) {
	if(n <= 2)
        return n;
    int[] dp = new int[n+1];
    int f1 = 1, f2 = 2;
    int i = 3;
    while(i <= n) {
        dp[i] = dp[i-1] + dp[i-2];
        i++;
    }
    return dp[n];
}
Copy the code

Case 2: DP of a two-dimensional array

A robot is located in the upper left corner of an M x N grid. Robots can only move one step down or one step to the right at a time. The robot tries to reach the lower right corner of the mesh. How many different paths are there?

  1. When the robot walks from the upper left corner to (I, j), there are all kinds of dp[I] [j] paths.
  2. State transition equation: DP [I] [J] = DP [i-1] [J] + DP [I] [J-1]
  3. Define the initial values: dp[0] [0, j, n-1] = 1, dp[0, j, m-1] [0] = 1
uniquePaths(int m, int n) {
    if(m <= 0 || n <= 0)
        return 0;
    int[][] dp = new int[m][n];
    
    for(int i = 0; i < m; i++) dp[i][0] = 1;
    for(int j = 0; j < n; j++) dp[0][j] = 1;
    
    for(int i = 1; i < m; i++) {for(int j = 1; j < n; j++) { dp[i][j] = dp[i-1][j] + dp[i][j-1]; }}return dp[m-1][n-1];
}
Copy the code

How to optimize dynamic programming

When you use arrays, you don’t need to save values that you won’t need again, reducing space complexity. For example, in case 2, when we calculate the values of row I, we only use the values of row i-1, but not the values of rows 1 to 2. Therefore, we can only use a one-dimensional array to store the values of the previous row. During the calculation, we need to constantly update the values of dp[].