Dynamic planning has three elements

Three steps:

1. Defining the meaning of DP
2. Find the boundary conditions
3. Find recursion

1. Climb the stairs

Leetcode-cn.com/problems/cl…

class Solution {
    public int climbStairs(int n) {
        if(n < 2) return 1;
        // dp[n] indicates how many ways there are to climb the NTH stair
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        
        //dp[n] = dp[n-1] + dp[n-2]
        for(int i = 2; i <=n ; i++) dp[i] = dp[i-1] + dp[i-2];
        returndp[n]; }}Copy the code

2. Maximum suborder sum

Leetcode-cn.com/problems/ma…

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        // dp[I] represents the sum of subarrays ending with nums[I]
        int[] dp = new int[n];
        dp[0] = nums[0];
        int res = Integer.MIN_VALUE;
        for(int i = 1 ; i < n ; i++){
            dp[i] = Math.max(dp[i-1].0) + nums[i];
        }
        // Find the maximum value in the dp array
        for(int num : dp) res = Math.max(res , num);
        returnres; }}class Solution {
    public int maxSubArray(int[] nums) {
        int res = Integer.MIN_VALUE;
        int sum = 0;
        for(int num : nums){
            if(sum > 0) sum += num;
            else sum = num;

            res = Math.max(res , sum);
        }
        returnres; }}Copy the code

3. Maximum subarray of product

Leetcode-cn.com/problems/ma…

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        int res = Integer.MIN_VALUE;
        int min = 1 , max = 1;
        for(int i = 0 ; i < n ; i++){
            if(nums[i] < 0) {int tem = min;
                min = max;
                max = tem;
            }

            min = Math.min(nums[i] , nums[i]*min);
            max = Math.max(nums[i] , nums[i]*max);
            res = Math.max(res , max);
        }
        returnres; }}Copy the code

3. Different paths

Leetcode-cn.com/problems/un…

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

4. Different path 2

Leetcode-cn.com/problems/un…

class Solution {
    public int uniquePathsWithObstacles(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        if(row == 0 || col == 0) return 0;
        int[][] dp = new int[row][col];

        for(int i = 0 ; i < row ; i++) {
            if (matrix[i][0] != 1) dp[i][0] = 1;
            else break;
        }

        for(int i = 0 ; i < col ; i++){
            if(matrix[0][i] ! =1) dp[0][i] = 1;
            else break;
        }

        for(int i = 1 ; i < row ; i++){
            for(int j = 1; j < col ; j++){if(matrix[i][j] ! =1) dp[i][j] = dp[i-1][j] + dp[i][j-1]; }}return dp[row-1][col-1]; }}Copy the code

5. Minimum path sum

Leetcode-cn.com/problems/mi…

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        if(m == 0 || n == 0) return 0;
        int[][] dp = new int[m][n];
        dp[0] [0] = grid[0] [0];
        for(int i = 1 ; i < m ; i++) dp[i][0] = dp[i-1] [0] + grid[i][0];
        for(int j = 1 ; j < n ; j++) dp[0][j] = dp[0][j-1] + grid[0][j];

        for(int i = 1; i < m ; i++){
            for(int j = 1; j < n ; j++){ dp[i][j] = Math.min(dp[i-1][j] , dp[i][j-1]) + grid[i][j]; }}return dp[m-1][n-1]; }}Copy the code

6. Minimum path sum of triangles

Leetcode-cn.com/problems/tr…

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int row = triangle.size();
        int col = triangle.get(row-1).size();
        int[][] dp = new int[row][col];

        dp[0] [0] = triangle.get(0).get(0);
        for(int i = 1 ; i < row ; i++){
            for(int j = 0; j <= i ; j++){if(j == i) dp[i][j] = dp[i-1][j-1] + triangle.get(i).get(j);
                else if(j == 0) dp[i][j] = dp[i-1][j] + triangle.get(i).get(j);
                else dp[i][j] = Math.min(dp[i-1][j-1] , dp[i-1][j]) + triangle.get(i).get(j); }}int res = Integer.MAX_VALUE;
        for(int i = 0 ; i < col ; i++){
            res = Math.min(res , dp[row-1][i]);
        }
        returnres; }}Copy the code

7. Robbery

Leetcode-cn.com/problems/ho…

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        if(n == 1) return nums[0];
        //dp[I] indicates the maximum amount of money stolen from nums[I]
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0] , nums[1]);
        for(int i = 2 ; i < n ; i++){
            dp[i] = Math.max(dp[i-1] , dp[i-2] + nums[i]);
        }
        return dp[n-1]; }}Copy the code

8. Robbery 2

Leetcode-cn.com/problems/ho…

class Solution {
    public int rob(int[] nums) {
        int n  = nums.length;
        if(n == 0) return 0;
        if(n == 1) return nums[0];
        if(n == 2) return Math.max(nums[0],nums[1]);

        // Steal the first, not the last
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0] , nums[1]);
        for(int i = 2;  i < n-1; i++) dp[i] = Math.max(dp[i-1],dp[i-2] + nums[i]);
        int res = dp[n-2];

        // Don't steal the first, steal the last
        int[] dp1 = new int[n];
        dp1[0] = 0;
        dp1[1] = nums[1];
        dp1[2] = Math.max(nums[1] , nums[2]);
        for(int i = 2 ; i < n ; i++) dp1[i] = Math.max(dp1[i-1] , dp1[i-2] + nums[i]);
        int res1 = dp1[n-1]; 
        returnMath.max(res , res1); }}Copy the code

9. Edit distance

Leetcode-cn.com/problems/ed…

class Solution {
    public int minDistance(String s, String p) {
        int ls = s.length();
        int lp = p.length();
        // dp[I][j] indicates the distance between s[0-i] and p[0-j]
        int[][] dp = new int[ls+1][lp+1];
        dp[0] [0] = 0;

        for(int i = 0 ; i <= ls ; i++) dp[i][0] = i;
        for(int j = 0 ; j <= lp ; j++) dp[0][j] = j;

        for(int i = 1; i <= ls ; i++){
            for(int j = 1; j <= lp ; j++){if(s.charAt(i-1) == p.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = Math.min(dp[i-1][j-1] , Math.min(dp[i-1][j] , dp[i][j-1+))1; }}returndp[ls][lp]; }}Copy the code

10. Decoding method

Leetcode-cn.com/problems/de…

class Solution {
    public int numDecodings(String s) {
         int n = s.length();
        if (n == 0) return 0;
        int[] dp = new int[n+1];
        dp[0] = 1;
        for (int i = 1; i <= n ; i++) {
            //1. There is no letter corresponding to 0, so if the last letter is 0, just add the preceding one
            if (s.charAt(i-1) != '0') dp[i] += dp[i-1];
            if (i >= 2) {Dp [i-1] = dp[i-2] = dp[i-1]
                int num = Integer.parseInt(s.substring(i-2 , i));
                if (num >= 10 && num <= 26) dp[i] += dp[i-2]; }}returndp[n]; }}Copy the code

11. Egg throwing — reverse DP

Leetcode-cn.com/problems/su…

class Solution {
    public int superEggDrop(int K, int N) {
// dp[k][m] = n
// # there are currently k eggs, and you can try throwing them m times
// # in this state, a maximum of n floors can be tested

[1][7] = 7
// # now have 1 egg, allow you to throw 7 times;
// # this state can give you up to 7 floors,
// # so that you can determine the floor F so that the egg does not break
// # (layer by layer)

        // // finally determine the number of eggs thrown, which is m
        // int m = 0;
        // while(dp[k][m] < N){
        // m++;
        // // Recursive formula
        // //1, no matter which floor you throw eggs, eggs can only be broken or not broken, broken words to measure downstairs, not broken words to measure upstairs.
        // //2, whether you go upstairs or downstairs, total number of floors = number of floors upstairs + number of floors downstairs + 1 (current floor)
        // // dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1
        // //dp[k][m-1] is the number of floors upstairs, because the number of eggs k is constant, that is, eggs are not broken, the number of eggs thrown m minus one;
        // //dp[k-1][m-1] is the number of floors below, because the number of eggs k minus one, that is, the eggs break, and the number of eggs thrown at the same time m minus one

        // }
        // return m; Dp [K][m] == N

        // m cannot exceed N times at most (linear scan)
        int[][] dp = new int[K + 1][N + 1];
        // base case:
        // dp[0][..] = 0
        // dp[..] [0] = 0
        // Java initializes arrays to 0 by default
        int m = 0;
        while (dp[K][m] < N) {
            m++;
            for (int k = 1; k <= K; k++)
                dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
        }
        returnm; }}Copy the code

The second part, the change problem

1. Change

Leetcode-cn.com/problems/co… There is an infinite number of coins of each kind

class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        // Add the amount+1 method number
        int[] dp = new int[amount+1];
        Arrays.fill(dp , amount+1);
        dp[0] = 0;
        for(int i = 1 ; i <= amount ; i++){
            for(int coin : coins){
                if(coin <= i) dp[i] = Math.min(dp[i] , dp[i-coin]+1); }}return dp[amount] == amount+1 ? -1: dp[amount]; }}Copy the code

2. Change 2

Leetcode-cn.com/problems/co…

class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for(int i = 0 ; i < n ; i++){
            for(int j = 1; j <=amount ; j++){if(j - coins[i] >= 0) dp[j] = dp[j] + dp[j-coins[i]]; }}returndp[amount]; }}Copy the code

The third part, subset segmentation, subsequence problems

1. Split equal and subset

Leetcode-cn.com/problems/pa…

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int num : nums) sum += num;
        if(sum % 2= =1) return false;
        int n = nums.length;
        sum = sum/2; // Just pack half sum
        //dp[I][j] indicates whether the sum of the preceding I numbers equals j
        boolean[][] dp = new boolean[n+1][sum+1];
        for(int i = 0 ; i <= n ; i++) dp[i][0] = true;
        for(int i = 1; i <= n ; i++){
            for(int j = 1; j<= sum ; j++){if(j - nums[i-1] < 0) dp[i][j] = dp[i-1][j]; // Can not load the backpack, can only see the previous value is ok
                else dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]].// Load or not load}}returndp[n][sum]; }}Copy the code

2. Longest increasing subsequence

Leetcode-cn.com/problems/lo…

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        //dp[I] represents the longest increasing subsequence ending with nums[I]
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        for(int i = 1; i < n ; i++){for(int j = i-1; j >=0; j--){if(nums[i] > nums[j]) dp[i] = Math.max(dp[i] , 1+dp[j]); }}int res = 1;
        for(int num : dp) res = Math.max(res , num);
        returnres; }}Copy the code

3. The Russian nesting envelope problem

Leetcode-cn.com/problems/ru…

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if(envelopes.length == 0) return 0;
        // Note that if they are equal, they are sorted in descending order
        Arrays.sort(envelopes,(a,b) -> (a[0] == b[0]? b[1]-a[1] : a[0]-b[0]));

        int[] nums = new int[envelopes.length];
        int index = 0;
        for(int[] num : envelopes) nums[index++] = num[1];

        // Find the longest increasing subsequence
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp , 1);
        for(int i = 1; i < n ; i++){for(int j = i-1 ; j >= 0; j--){if(nums[i] > nums[j]) dp[i] = Math.max(dp[i] , 1+dp[j]); }}int res = 1;
        for(int num : dp) res = Math.max(res , num);
        returnres; }}Copy the code

4. Longest common subarray

Leetcode-cn.com/problems/ma…

class Solution {
    public int findLength(int[] A, int[] B) {
        int la = A.length;
        int lb = B.length;
        //dp[I][j] represents the longest common subarray ending with A[I] and B[j]
        int[][] dp = new int[la+1][lb+1];
        dp[0] [0] = 0;
        int res = 0;
        for(int i = 1; i <= la ; i++){
            for(int j = 1; j <= lb ; j++){if(A[i-1] == B[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = 0; res = Math.max(res , dp[i][j]); }}returnres; }}Copy the code

5. Longest common subsequence

Leetcode-cn.com/problems/lo…

class Solution {
    public int longestCommonSubsequence(String s, String p) {
        int ls = s.length();
        int lp = p.length();
        //dp[I][j] represents the longest common subsequence length of s[0-i] and p[0-j]
        int[][] dp = new int[ls+1][lp+1];
        dp[0] [0] = 0;
        for(int i = 1 ; i <= ls ; i++){
            for(int j = 1 ; j <= lp ; j++){
                if(s.charAt(i-1) == p.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = Math.max(dp[i-1][j] , dp[i][j-1]); }}returndp[ls][lp]; }}Copy the code

The fourth part, the problem of the substring

1. The longest subroutine

Leetcode-cn.com/problems/lo…

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if(n == 0) return "";
        //dp[I][j] indicates whether s[i-j] is a palindrome
        boolean[][] dp = new boolean[n][n];
        for(int i = 0; i < n ; i++) dp[i][i] =true;

        int maxlen = 1;
        int start = 0;

        for(int i = n-2 ; i >= 0 ; i--){
            for(int j = i+1; j < n ; j++){if(s.charAt(i) ! = s.charAt(j)) dp[i][j] =false;
                else{
                    if(j - i < 3) dp[i][j] = true;
                    else dp[i][j] = dp[i+1][j-1];
                }

                if(dp[i][j] && j-i+1 > maxlen){
                    maxlen = j-i+1; start = i; }}}returns.substring(start , start + maxlen); }}Copy the code

2. Longest sequence of rhymes

Leetcode-cn.com/problems/lo…

class Solution {
    public int longestPalindromeSubseq(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        //1. Dp [I][j] represents the longest sequence length between chars[I] and chars[j]
        int[][] dp = new int[n][n];
        / / 2. The initialization
        for(int i = 0 ; i < n ; i ++) dp[i][i] = 1;
        //3. I precedes j
        for(int i = n-2 ; i >= 0 ; i--){
            for(int j= i+1 ; j < n ; j++){
                if(chars[i] == chars[j]) dp[i][j] = dp[i+1][j-1] + 2;
                else dp[i][j] = Math.max(dp[i+1][j] , dp[i][j-1]); }}return dp[0][n-1]; }}Copy the code

3. Number of subracks

Leetcode-cn.com/problems/pa…

class Solution {
    public int countSubstrings(String s) {
        int res = 0;
        int n = s.length();

        boolean[][] dp = new boolean[n][n];
        for(int i = 0 ; i < n ; i++){
            dp[i][i] = true;
            res++;
        }

        for(int i = n-2 ; i >= 0; i--){for(int j = i+1; j < n ; j++){if(s.charAt(i) ! = s.charAt(j)) dp[i][j] =false;
                else{
                    if(j - i < 3) dp[i][j] = true;
                    else dp[i][j] = dp[i+1][j-1];
                }
                if(dp[i][j]) res++; }}returnres; }}Copy the code

4. The minimum number of insertions to make a string palindrome

Leetcode-cn.com/problems/mi…

class Solution {
    public int minInsertions(String s) {
        // Find the longest sequence of subroutines, and subtract
        int n = s.length();
        int m = maxHuiWen(s);
        return n-m;
    }

    int maxHuiWen(String s){
        char[] chars = s.toCharArray();
        int n = chars.length;
        int[][] dp = new int[n][n];
        for(int i = 0 ; i < n ; i++) dp[i][i] = 1;

        for(int i = n-2 ; i >= 0 ; i--){
            for(int j = i+1; j < n ; j++){if(chars[i] == chars[j]) dp[i][j] = dp[i+1][j-1] + 2;
                else dp[i][j] = Math.max(dp[i+1][j] , dp[i][j-1]); }}return dp[0][n-1]; }}Copy the code

5. The minimum number of times to split palindromes

Leetcode-cn.com/problems/pa…

class Solution {
    public int minCut(String s) {
        int n = s.length();
        if(n < 2) return 0;
        int[] dp = new int[n];
        //base case: split each character
        for(int i = 0 ; i < n ; i++) dp[i] = i;

        boolean[][] dp2 = new boolean[n][n];
        for (int r = 0 ;  r < n ; r++){
            for (int l = 0; l <= r ; l++){if (s.charAt(l) == s.charAt(r) && (r-l <= 2 || dp2[l+1][r-1])) dp2[l][r] = true; }}for (int i = 1; i < n; i++) {
            if (dp2[0][i]){ // If from 0 - I is already palindrome
                dp[i] = 0;
                continue;
            }
            for (int j = 0; j < i; j++) {
                if (dp2[j+1][i]){
                    dp[i] = Math.min(dp[i] , dp[j]+1); }}}return dp[n-1]; }}Copy the code

The fifth part, the problem of string matching

1. Match regular expressions

Leetcode-cn.com/problems/re…

class Solution {
    public boolean isMatch(String s, String p) {
        int ls = s.length();
        int lp = p.length();

        boolean[][] dp = new boolean[ls+1][lp+1];
        dp[0] [0] = true;
        // "" "a*" A * can match an empty string
        for(int i = 2 ; i <= lp ; i++) dp[0][i] = dp[0][i-2] && p.charAt(i-1) = =The '*';

        for(int i = 1 ; i <= ls ; i++){
            for(int j = 1; j<= lp ; j++){int m = i-1 , n = j-1;
                if(p.charAt(n) == The '*'){
                    dp[i][j] = dp[i][j-2]  // Matches the empty string
                    || (dp[i-1][j] && (s.charAt(m) == p.charAt(n-1) || p.charAt(n-1) = ='. '));
                       // Match one or more matches before
                }else if(p.charAt(n) == '. ' || s.charAt(m) == p.charAt(n)) dp[i][j] = dp[i-1][j-1]; }}returndp[ls][lp]; }}Copy the code

2. Break up words

Leetcode-cn.com/problems/wo…

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {

        int ls =  s.length();
        boolean[] dp = new boolean[ls+1];
        dp[0] = true;
        for(int i = 1 ; i <= ls ; i++){
            for(int j = i-1 ; j >= 0 ; j--){
                String tem = s.substring(j , i);
                if(wordDict.contains(tem) && dp[j]){
                    dp[i] = true;
                    break; }}}returndp[ls]; }}Copy the code

3. Interleaved string

Leetcode-cn.com/problems/in…

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n1 = s1.length();
        int n2 = s2.length();
        int n3 = s3.length();

        if(n1 + n2 ! = n3)return false;
        boolean[][] dp = new boolean[n1+1][n2+1];
        dp[0] [0] = true;

        for(int i = 1; i <= n1 ; i++){ dp[i][0] = dp[i-1] [0] && s1.charAt(i-1) == s3.charAt(i-1);
        }
        for(int i = 1; i <= n2 ; i++){
            dp[0][i] = dp[0][i-1] && s2.charAt(i-1) == s3.charAt(i-1);
        }
        for(int i = 1; i <= n1 ; i++){
            for(int j = 1; j <= n2 ; j++){
                dp[i][j] = dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i-1+j)
                         || dp[i][j-1] && s2.charAt(j-1) == s3.charAt(j-1+i); }}returndp[n1][n2]; }}Copy the code