Dynamic programming chapter 4: different paths + different paths (with obstacles) + integer split + different binary search tree

The article directories

• • • 62. Different paths
    • 63. Different paths II
    • 343. Integer splitting
    • 96. Different binary search trees

62. Different paths

A robot is located in the upper left corner of an M x N grid (the starting point is marked “Start” in the figure below).

The robot can only move one step to the right or down at a time. The robot attempts to reach the lower right corner of the grid (marked “Finish” in the image below).

How many different paths are there?

Example: Input: m = 3, n = 2 Output: 3 Description: There are three paths to the lower right corner starting from the upper left corner.

Right -> right -> down right -> down -> right down -> right down -> right -> right

The robot starts at (0, 0) and ends at (m-1, n-1).

According to the analysis of the five parts of the moving gauge:

1. Dp [I][j] : indicates that there are dp[I][j] paths from (0, 0) to (I, j).
2. To determine the recursive formula dp[I][j], only two directions can be derived, namely DP [i-1][j] and DP [I][J-1].

There are several paths from position (0, 0) to position (I – 1, j), dp[I][j-1].

So naturally, dp [I] [j] = dp [j] + [I – 1] dp [1], [I] because the dp [I] [j] only the two direction.

3. First, dp[I][0] must always be 1, because there is only one path from position (0, 0) to position (I, 0), so dp[0][j] should also be initialized.

So the initialization code is:

for (int i = 0; i < m; i++) dp[i][0] = 1;

for (int j = 0; j < n; j++) dp[0][j] = 1;

4. The recursive formula dp[I][j] = dp[i-1][j] + dp[I][j-1], dp[I][j] is derived from the upper and left side of it, so it can be traversed layer by layer from left to right.

This guarantees that dp[i-1][j] and DP [I][j-1] must have numerical values when deducing dp[I][j].

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp=new int[m][n];
        for(int i=0; i<m; i++) dp[i][0]=1;for(int i=0; i<n; i++) dp[0][i]=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]; }}returndp[m-1][n-1]; }}Copy the code

63. Different paths II

class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m=obstacleGrid.length; int n=obstacleGrid[0].length; int[][] dp=new int[m][n]; // Initialize each data to 0for(int i=0; i<m; i++){if(obstacleGrid[I][0]==0) // 0 indicates that there is no barrier. If the barrier is 1, it indicates that it cannot be reached, which is the default 0 dp[I][0]=1;else break; // Because the boundary position is only one path, so the behind is not reachable, even if the behind is not an obstacle, it should be 0}for(int j=0; j<n; j++){if (obstacleGrid[0][j]==0)
                dp[0][j]=1;
            else break; // Because the boundary position is only one path, so the behind is not reachable, even if the behind is not an obstacle, it should be 0}for(int i=1; i<m; i++){for(int j=1; j<n; j++){if(obstacleGrid [I] [j] = = 0) / / if the obstruction is 1, cannot reach here, is the default 0 dp [I] [j] = dp [I]] [j - 1 + dp [I - 1] [j]; // The middle node has two paths, so it is not directelse break; }}returndp[m-1][n-1]; }}Copy the code

343. Integer splitting

Given a positive integer n, split it into the sum of at least two positive integers and maximize the product of these integers. Returns the largest product you can get.

Example 1: Input: 2 Output: 1 Description: 2 = 1 + 1, 1 x 1 = 1.

Example 2: Input: 10 Output: 36 Description: 10 = 3 + 3 + 4, 3 x 3 x 4 = 36. Note: You can assume that n is not less than 2 and not greater than 58.

Consider: the number of split is not specified, split into two, or three, or four…

Class Solution {public int int break (int n) {// n [2,58] //if (n==2) return1; There's no need to come backreturnInt [] dp = new int[n + 1]; Dp [2,58] dp[2] = 1; // dp[0] dp[1for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i ; j++)
                dp[i] = Math.max(dp[i], Math.max((i - j) * j, dp[i - j] * j));
        }
        returndp[n]; // if n is given 2, return dp[2]; if n is given other values, return dp[n]}}.Copy the code

If (n==2) return 1; There is no need to return dp[n] when n==2, we can return dp[2].

Note 2: the array must be defined to specify the length, where dp[I] is defined to mean splitting the number I, the largest product that can be obtained is dp[I]. Therefore, the final return should be dp[n], so we should define the length as new int[n+1].

For (int I = 3; i <= n; I ++) (1) since dp[0] dp[1] has no meaning, dp[2]=1 is used as the initial value, so I starts at 3 (2) because dp[n] is returned at the end, the loop condition is I <=n instead of I

For (int j = 1; j < i – 1; J ++) (1) Because we split the current number I, we start with I =1 + (I -1), so j starts at 1, and when j=1, I -j = I -1; (2) I =1 + (i-1), so j to i-1, when j=i-1, i-j=1; Why can I also write j to I minus 2? Because (3) j goes from small to big, so j++.

Note 5: dp [I] = math.h Max (dp [I], Math. Max ((I – j) * j, dp/I – j * j)); (1) math.max ((i-j) * j, dp[i-j] * j) (i-j) * j = (i-j) * j = (i-j) * j = (i-j) * j Dp [i-j] * j = dp[i-j] * j = dp[i-j] * j Finally, math.max is used to extract the maximum value of I for only one tear and multiple tear. (2) Math. Max (dp [I], Math. Max ((I – j) * j, dp/I – j * j)); The new dp[I] is compared with the old maximum dp[I], and the larger dp[I] is stored in dp[I].

96. Different binary search trees

Class Solution {public int numTrees(int n) {// n [1,19] int[] dp=new int[n+1]; dp[0]=1; // There is nothing that can't be 0. This is for multiplicationfor(int i=1; i<=n; i++){for(int j=1; j<=i; j++) dp[i]=dp[i]+dp[i-j]*dp[j-1]; }returndp[n]; }}Copy the code