动态规划专题

快来打我* 2023-01-07 12:27 180阅读 0赞

# 动态规划 #

### 文章目录 ###

*  动态规划
 *   *  一，最大/最小问题
     *   *  1.1 \[使用最小花费爬楼梯\](https://leetcode-cn.com/problems/min-cost-climbing-stairs/)
         *  1.2 \[最小路径和\](https://leetcode-cn.com/problems/minimum-path-sum/)
         *  1.3 \[零钱兑换\](https://leetcode-cn.com/problems/coin-change/)
         *  1.4 \[下降路径最小和\](https://leetcode-cn.com/problems/minimum-falling-path-sum/)
         *  1.5 \[最低票价\](https://leetcode-cn.com/problems/minimum-cost-for-tickets/)
         *  1.6 \[只有两个键的键盘\](https://leetcode-cn.com/problems/2-keys-keyboard/)
         *  1.6 \[完全平方数\](https://leetcode-cn.com/problems/perfect-squares/)
         *  1.7 \[加油站\](https://leetcode-cn.com/problems/gas-station/)
         *  1.8 \[最大正方形\](https://leetcode-cn.com/problems/maximal-square/)
     *  二，背包问题
     *   *  2.1 \[最后一块石头的重量 II\](https://leetcode-cn.com/problems/last-stone-weight-ii/)
         *  2.2 \[一和零\](https://leetcode-cn.com/problems/ones-and-zeroes/)
     *  三，求解解决问题的方式有多少种
     *   *  3.1 \[爬楼梯\](https://leetcode-cn.com/problems/climbing-stairs/)
         *  3.2\[不同路径\](https://leetcode-cn.com/problems/unique-paths/)
         *  3.3\[不同路径 II\](https://leetcode-cn.com/problems/unique-paths-ii/)
         *  3.4\[目标和\](https://leetcode-cn.com/problems/target-sum/)
         *  3.5 \[“马”在棋盘上的概率\](https://leetcode-cn.com/problems/knight-probability-in-chessboard/)
         *  3.6\[组合总和 Ⅳ\](https://leetcode-cn.com/problems/combination-sum-iv/)
         *  3.7\[最长上升子序列\](https://leetcode-cn.com/problems/longest-increasing-subsequence/)
         *  3.8\[最长递增子序列的个数\](https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/)
     *  四，区间合并
     *   *  4.1\[叶值的最小代价生成树\](https://leetcode-cn.com/problems/minimum-cost-tree-from-leaf-values/)
         *  4.2\[不同的二叉搜索树\](https://leetcode-cn.com/problems/unique-binary-search-trees/)
     *  五，序列问题
     *   *  5.1\[最长公共子序列\](https://leetcode-cn.com/problems/longest-common-subsequence/)
         *  5.2\[回文子串\](https://leetcode-cn.com/problems/palindromic-substrings/)
         *  5.3\[最长回文子串\](https://leetcode-cn.com/problems/longest-palindromic-substring/)
         *  5.4\[最长回文子序列\](https://leetcode-cn.com/problems/longest-palindromic-subsequence/)
         *  5.5\[编辑距离\](https://leetcode-cn.com/problems/edit-distance/)
     *  六，决定问题
     *   *  6.1\[打家劫舍\](https://leetcode-cn.com/problems/house-robber/)
         *  6.2\[打家劫舍 II\](https://leetcode-cn.com/problems/house-robber-ii/)
         *  6.3\[打家劫舍 III\](https://leetcode-cn.com/problems/house-robber-iii/)

## 一，最大/最小问题 ##

模板：

for (int i = 1; i <= target; ++i) {
        
       for (int j = 0; j < ways.size(); ++j) {
        
           if (ways[j] <= i) {
        
               dp[i] = min(dp[i], dp[i - ways[j]] + cost / path / sum) ;
           }
       }
    }
    return dp[target]

### 1.1 [使用最小花费爬楼梯][Link 1] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70]

状态定义：

dp[i]：到达第i级台阶需要的最小花费，第i级台阶是第i-1级台阶的阶梯顶部。

递推方程推导思路：

- 可以跨一级：dp[i - 1]
    	- 可以跨两级：dp[i - 2]
    	- 那么dp[i]可以是跨两级上来第i级，也可以是跨一级上来的，所以：
    	- dp[i] = Min(dp[i - 1],dp[i - 2]) + cost[i]
    	- 注意，第array.length级台阶是第array.length - 1级台阶顶部，所以要想登上还需要跨过去，设这个为一个花费为0的虚拟台阶
    	- dp[i] = Min(dp[i - 1],dp[i - 2]) + (i == array.length ? 0 : cost[i])

初始状态处理：

dp[0] = cost[0]
    dp[1] = cost[1]

实现：

public int minCostClimbingStairs(int[] cost) {
        
            if(cost.length == 0){
        
                return 0;
            }
            if(cost.length == 1){
        
                return cost[0];
            }
            if(cost.length == 2){
        
                return Math.min(cost[0],cost[1]);
            }
            int n = cost.length;
            int[] dp = new int[n+1];
            dp[0] = cost[0];
            dp[1] = cost[1];
            for(int i = 2;i <= n;i++){
        
                dp[i] = Math.min(dp[i - 1],dp[i - 2]) + (i == n ? 0 : cost[i]);
            }
            return dp[n];
        }

### 1.2 [最小路径和][Link 2] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 1]

状态定义：

dp[i][j]：走到第i行第j列路径的最小总和

初始状态：

// 如果只有一行，那么直接沿着这一行到底
    	    int n = grid[0].length;
            for(int i = 1;i < n;i++){
                dp[0][i] = dp[0][i - 1] + grid[0][i];
            }
            // 如果只有一列
            dp[0][0] = grid[0][0];
            for(int i = 1;i < m;i++){
                dp[i][0] = dp[i - 1][0] + grid[i][0];
            }

状态方程：

dp[i][j] = Math.min(dp[i - 1][j],dp[i][j - 1]) + grid[i][j];

实现：

public int minPathSum(int[][] grid) {
        
            if(grid.length == 0){
        
                return 0;
            }
            int m = grid.length;
            int n = grid[0].length;
            int[][] dp = new int[m+1][n+1];
            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 i = 1;i < n;i++){
        
                dp[0][i] = dp[0][i - 1] + grid[0][i];
            }
            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][n];
        }

### 1.3 [零钱兑换][Link 3] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 2]

状态定义：

dp[i]：金额为i元时需要的最少硬币数

状态方程：

两种状态：要么兑换要么不兑换，比较两者所需硬币的最小值
    for n in coins:
    	if i >= coins[n]:
    		dp[i] = min(dp[i],dp[i - coins[n]] + 1)

实现：

public int coinChange(int[] coins, int amount) {
        
            int[] dp = new int[amount + 1];
            Arrays.fill(dp, amount + 1);
            dp[0] = 0;
            for(int i = 1;i <= amount;i++){
        
                for(int j = 0;j < coins.length;j++){
        
                    if(i >= coins[j]){
        
                        dp[i] = Math.min(dp[i],dp[i - coins[j]] + 1);
                    }
                }
            }
            return dp[amount] > amount ? -1 : dp[amount];
        }

### 1.4 [下降路径最小和][Link 4] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 3]

状态定义：

dp[i][j]：到（i，j）位置的最小路径和

状态方程：

dp[i][j]可以从(i-1,j)下来，可以从(i-1,j-1)下来，可以从(i-1,j+1)下来
    dp[i][j] = min(dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1]) + A[i][j]

实现：

public int minFallingPathSum1(int[][] A) {
        
            // 设dp[i][j]为到i, j位置的最小路径和
            int len = A.length;
            int[][] dp = new int[len + 1][len + 2];
            
            for (int i = 0; i < len + 1; i++) {
        
                dp[i][0] = Integer.MAX_VALUE;
                dp[i][len + 1] = Integer.MAX_VALUE;
            }
            for (int j = 0; j < len + 2; j++) {
        
                dp[0][j] = 0;
            }
    
            int ans = Integer.MAX_VALUE;
            for (int i = 1; i < len + 1; i++) {
        
                for (int j = 1; j < len + 1; j++) {
        
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + A[i - 1][j - 1];
                }
            }
            for (int i = 1; i < len + 1; i++) {
        
                ans = Math.min(ans, dp[len][i]);
            }
            return ans;
        }

### 1.5 [最低票价][Link 5] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 4]

状态定义：

dp[i]: 第i天旅行最少花费多少元

状态方程：

第n天去旅行： dp[ n ]=min( dp[ n-1 ] + cost[ 0 ] , dp[ n-7 ] + cost[ 1 ] , dp[ n-30 ] + cost[ 2 ] )
    第n天不去旅行：dp[n] = dp[n - 1]

实现：

public int mincostTickets(int[] days, int[] costs) {
        
            // 第n天去旅行： dp[ n ]=min( dp[ n-1 ] + cost[ 0 ] , dp[ n-7 ] + cost[ 1 ] , dp[ n-30 ] + cost[ 2 ] )
            // 第n天不去旅行：dp[n] = dp[n - 1]
            int[] dp = new int[396];
            // day数组下标
            int index = 0;
            for(int i = 31;index < days.length && i <= 395;i++){
        
                if(days[index] != i - 30){
        
                    // 第i天不需要旅行
                    dp[i] = dp[i - 1];
                    continue;
                }
                index++;
                dp[i] = Math.min(dp[i - 1] + costs[0],Math.min(dp[i - 7] + costs[1],dp[i - 30] + costs[2]));
            }
            return dp[days[days.length - 1] + 30];
        }

### 1.6 [只有两个键的键盘][Link 6] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 5]

状态定义：

dp[i]：得到i个字符所需的最少操作次数

状态方程：

如果是素数：dp[i] = i;
    如果是合数：dp[i] = dp[j] + dp[i / j];

实现：

public int minSteps(int n) {
        
            int[] dp = new int[n + 1];
            // dp[i]：得到i个字符最少需要几步操作
            int h = (int) Math.sqrt(n);
            for (int i = 2; i <= n; i++) {
        
                dp[i] = i;
                for (int j = 2; j <= h; j++) {
        
                    // 质数：dp[i]，得到i个字符最少需要i步操作
                    if (i % j == 0) {
        
                        // 合数：dp[i]：将i分解到不能分解质因数的操作次数
                        dp[i] = dp[j] + dp[i / j];
                        break;
                    }
                }
            }
            return dp[n];
        }

### 1.6 [完全平方数][Link 7] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 6]

状态定义：

dp[i]：找到dp[i]个完全平方数使得他们的和是i

状态转移方程：

dp[i] = min(dp[i],dp[i - j * j] + 1)

实现：

public int numSquares(int n) {
        
            if(n < 2){
        
                return n;
            }
            int[] dp = new int[n + 1];
            // dp[i]：找到dp[i]个完全平方数使得他们的和=i；
            for(int i = 0;i <= n;i++){
        
                dp[i] = i;
            }
            for(int i = 2;i <= n;i++){
        
                for(int j = 1;j * j <= i;j++){
        
                    dp[i] = Math.min(dp[i],dp[i - j * j] + 1) ;
                }
            }
            return dp[n];
        }

### 1.7 [加油站][Link 8] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 7]

思路：

cur：当前油量
    rest：剩余油量
    start：起始下标

过程分析：

cur：主要用来分析能不能走到下一个下标，如果不能即cur < 0，则需要更新起始下标，同时油缸油量从新从0开始：
    
    rest：遍历一次算出整体的gasSum - costSum，如果rest <= 0肯定是不能走完一圈的

实现：

public int canCompleteCircuit(int[] gas, int[] cost) {
        
            int cur = 0;
            int start = 0;
            int rest = 0;
            for(int i = 0;i < gas.length;i++){
        
                cur += (gas[i] - cost[i]);
                rest += (gas[i] - cost[i]);
                if(cur < 0){
        
                    cur = 0;
                    start = i + 1;
                }
            }
            return rest >= 0 ? start : -1;
        }

### 1.8 [最大正方形][Link 9] ###

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9Uw5BS4D-1610893042600)(C:%5CUsers%5C12642%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20200719223554043.png)\]

状态：

dp(i, j) 表示以 (i, j)(i,j) 为右下角，且只包含 11 的正方形的边长最大值

状态方程：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 8]

以（3,3）为右下角的正方形内部可能包含三个正方形

dp[i][j] = min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1]) + 1

实现：

public int maximalSquare(char[][] matrix) {
        
            //  dp(i,j) 表示以 (i, j)(i,j) 为右下角，且只包含 11 的正方形的边长最大值
            // dp[i][j] = min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1]) + 1
            if(matrix.length == 0 || matrix[0].length == 0){
        
                return 0;
            }
            int maxSide = 0;
            int[][] dp = new int[matrix.length][matrix[0].length];
            for(int i = 0;i < matrix.length;i++){
        
                for(int j = 0;j < matrix[0].length;j++){
        
                    if(matrix[i][j] == '1') {
        
                        if (i == 0 || j == 0) {
        
                            dp[i][j] = 1;
                        }else{
        
                            dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1;
                        }
                    }
                     maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
            return (int) Math.pow(maxSide,2);
        }

## 二，背包问题 ##

### 2.1 [最后一块石头的重量 II][II] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 9]

### 2.2 [一和零][Link 10] ###

## 三，求解解决问题的方式有多少种 ##

routes[i] = routes[i-1] + routes[i-2], ... , + routes[i-k]

### 3.1 [爬楼梯][Link 11] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 10]

状态定义：

dp[n]：爬到第n级台阶有多少种方法

状态方程：

dp[i] = dp[i - 1] + dp[i - 2]

实现：

public int climbStairs(int n) {
        
            if(n == 1){
        
                return 1;
            }
            if(n == 2){
        
                return 2;
            }
            int[] dp = new int[n + 1];
            dp[0] = 1;
            dp[1] = 1;
            for(int i = 2;i <= n;i++){
        
                dp[i] = dp[i - 1] + dp[i - 2];
            }
            return dp[n];
        }
    }

### 3.2[不同路径][Link 12] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 11]

状态定义：

dp[i][j]：到达（i，j）有多少种路径

状态方程：

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

实现：

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];
                }
            }
            return dp[m - 1][n - 1];
        }

### 3.3[不同路径 II][II 1] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 12]

状态定义：

dp[i][j]：到达（i，j）有多少种路径

状态方程：

if obstacleGrid[i][j] == 0
    	dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    else
    	dp[i][j] = 0;

实现：

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            int[][] dp = new int[m][n];
            // 注意入口和出口可能有障碍
            for(int i = 0;i < m && obstacleGrid[i][0] == 0;i++){
        
                dp[i][0] = 1;
            }
            for(int i = 0;i < n && obstacleGrid[0][i] == 0;i++){
        
                dp[0][i] = 1;
            }
            for(int i = 1;i < m;i++){
        
                for(int j = 1;j < n;j++){
        
                    if(obstacleGrid[i][j] != 1){
        
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    }else{
        
                        dp[i][j] = 0;
                    }
                }
            }
            return dp[m - 1][n - 1];
        }

### 3.4[目标和][Link 13] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 13]

状态定义：

dp[i]：当目标和为i时，有多少种方式

状态方程：

for num in nums:
    	dp[i] += dp[i - num]

实现：

public int findTargetSumWays(int[] nums, int S) {
        
            int sum = 0;
            for (int num : nums) {
        
                sum += num;
            }
            if (sum < S || (sum + S) % 2 == 1) {
        
                return 0;
            }
            int w = (sum + S) / 2;
            int[] dp = new int[w + 1];
            dp[0] = 1;
            for (int num : nums) {
        
                for (int j = w; j >= num; j--) {
        
                    dp[j] += dp[j - num];
                }
            }
            return dp[w];
        }

### 3.5 [“马”在棋盘上的概率][Link 14] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 14]

状态定义：

dp[i][j][k]：从i，j出发走k步还留在棋盘上的概率

状态方程：

if 从i，j出发走k步不留在棋盘上：
    	dp[i][j][k] = 0
    else
    	dp[i][j][k] = dp[i + x][j + y][k - 1] / 8  //x：正负2或者正负1，y：正负2或者正负1

实现：

public double knightProbability(int N, int K, int r, int c) {
        
            // 在第r，c位置经过k步后还停留在棋盘的概率
            int[][] dir = {
        {
        -2, -1}, {
        -2, 1}, {
        -1, 2}, {
        1, 2}, {
        2, 1}, {
        2, -1}, {
        1, -2}, {
        -1, -2}};
            double[][][] dp = new double[N][N][K + 1];
            for (int i = 0; i < N; i++) {
        
                for (int j = 0; j < N; j++) {
        
                    dp[i][j][0] = 1;
                }
            }
            for (int k = 1; k <= K; k++) {
        
                for (int i = 0; i < N; i++) {
        
                    for (int j = 0; j < N; j++) {
        
                        for (int d = 0; d < dir.length; d++) {
        
                            int nx = i + dir[d][0];
                            int ny = j + dir[d][1];
                            if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
        
                                dp[i][j][k] += (dp[nx][ny][k - 1]) / 8;
                            }
                        }
                        //提前返回
                        if (i == r && j == c && k == K) {
        
                            return dp[i][j][k];
                        }
                    }
                }
            }
            return dp[r][c][K];
        }

### 3.6[组合总和 Ⅳ][Link 15] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 15]

状态定义：

dp[i]：当总和为i时，组合个数

状态方程：

for j in nums:
    	if i >= num:
    		dp[i] += dp[i - num]

实现：

public int combinationSum4(int[] nums, int target) {
        
            int[] dp = new int[target+1];
            dp[0] = 1;
            for(int i = 1;i <= target;i++){
        
                for(int num : nums){
        
                    if(i >= num){
        
                        dp[i] += dp[i - num];
                    }
                }
            }
            return dp[target];
        }

### 3.7[最长上升子序列][Link 16] ###

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AvHMQEbX-1610893042603)(C:%5CUsers%5C12642%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20200726135123464.png)\]

状态定义：

dp[i]：当数组长度为i时的最长子序列长度

状态方程：

for i in nums:
    	 for j in range(i):
    		if i > j:
    			dp[i] = max(dp[j] + 1,dp[i])

实现：

public int lengthOfLIS(int[] nums) {
        
            if(nums.length <= 0){
        
                return 0;
            }
            // 当数组长度为i时，上升子序列的最长长度
            int[] dp = new int[nums.length + 1];
            // 自己一个数字也是一个子序列
            Arrays.fill(dp,1);
            for(int i = 1;i < nums.length;i++){
        
                for(int j = 0;j < i;j++){
        
                    if(nums[i] > nums[j]){
        
                        dp[i] = Math.max(dp[i],dp[j] + 1);
                    }
                }
            }
            int res = dp[0];
            for (int i = 0; i < nums.length; i++) {
        
                res = Math.max(res, dp[i]);
            }
            return res;
        }

### 3.8[最长递增子序列的个数][Link 17] ###

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-honl71tv-1610893042605)(C:%5CUsers%5C12642%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20200726141337385.png)\]

状态定义：

dp[i]：到第i个元素为止，最长子序列长度
    combination[j]：记录长度相同的子序列个数

实现：

public int findNumberOfLIS(int[] nums) {
        
            if (nums.length == 0) {
        
                return 0;
            }
            int[] dp = new int[nums.length];
            int[] combination = new int[nums.length];
            Arrays.fill(dp, 1);
            Arrays.fill(combination, 1);
            int max = 1, res = 0;
            for (int i = 1; i < dp.length; i++) {
        
                for (int j = 0; j < i; j++) {
        
                    if (nums[i] > nums[j]) {
        
                        if (dp[j] + 1 > dp[i]) {
         //如果+1长于当前LIS 则组合数不变
                            dp[i] = dp[j] + 1;
                            combination[i] = combination[j];
                        } else if (dp[j] + 1 == dp[i]) {
         //如果+1等于当前LIS 则说明找到了新组合
                            combination[i] += combination[j];
                        }
                    }
                }
                max = Math.max(max, dp[i]);
            }
    
            for (int i = 0; i < nums.length; i++)
                if (dp[i] == max) res += combination[i];
    
            return res;
        }

## 四，区间合并 ##

### 4.1[叶值的最小代价生成树][Link 18] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 16]

状态定义：

dp[i][j]：从i到j的最小和

状态方程：

从i到j最小和 = k节点左右两边元素中最大值的乘积 + 子问题k左边（i到k）最小值 * 子问题（k+1到j）最小值
    dp[i][i+d] = Math.min(dp[i][i+d], dp[i][k] + dp[k+1][i+d] + max(arr, i, k) * max(arr, k+1, i+d));

实现：

public int mctFromLeafValues(int[] arr) {
        
            // 从i到j最小和 = k节点左右两边元素中最大值的乘积 + 子问题k左边（i到k）最小值 * 子问题（k+1到j）最小值
            int n = arr.length;
            if(n == 0 || n == 1){
        
                return 0;
            }
            // dp[i][j]：从i到j的最小和
            int[][] dp = new int[n][n];
            for(int d = 1; d < n; ++d){
        
                for(int i = 0; i + d < n; ++i){
        
                    dp[i][i+d] = Integer.MAX_VALUE;
                    for(int k = i; k < i + d; ++k){
        
                        dp[i][i+d] = Math.min(dp[i][i+d], dp[i][k] + dp[k+1][i+d] + max(arr, i, k) * max(arr, k+1, i+d));
                    }
                }
            }
            return dp[0][n-1];
        }
    
        private int max(int[] arr, int begin, int end){
        
            int ans = 0;
            for(int i = begin; i <= end; i++){
        
                ans = Math.max(ans, arr[i]);
            }
            return ans;
        }

### 4.2[不同的二叉搜索树][Link 19] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 17]

状态定义：

dp[i]: 以n个节点去构造BST，能构造出多少种BST

状态方程：

dp[i] = dp[i-1] * dp[n-i-1]

实现：

public int numTrees(int n) {
        
            //return dfs(1,n);
            // 以n个节点去构造BST，能构造出多少种BST
            int[] dp = new int[n + 1];
            dp[0] = 1;// 空树也是一棵树
            dp[1] = 1;// 一个节点构造一棵树
            for(int i = 2;i <= n;i++){
        
                for(int j = 0;j < i;j++){
        
                    // dp[i] = dp[i-1] * dp[n-i-1]
                    dp[i] += dp[j] * dp[i - j - 1];
                }
            }
            return dp[n];
        }
    
        private int dfs(int start, int end) {
        
            if(start > end){
        
                return 1;
            }
            // 以i为根节点的左右子树的数量
            int sum = 0;
            for(int i = start;i <= end;i++){
        
                int left = dfs(start,i - 1);    // 以（i-1）-（start）个节点构造左子树
                int right = dfs(i + 1,end);     // 以（end）-（i+1）个节点构造右子树
                sum += left * right;            // 构建笛卡尔积
            }
            return sum;
        }

## 五，序列问题 ##

### 5.1[最长公共子序列][Link 20] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 18]

状态定义：

dp[i][j]：长度为i和j的字符串的最长公共子序列的长度

状态方程：

if s1[i - 1] == s2[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]);

实现：

public int longestCommonSubsequence(String text1, String text2) {
        
            // text1和text2的最长公共子序列长度
            int[][] dp = new int[text1.length() + 1][text2.length() + 1];
            // 初始化
            for(int i = 0;i < text1.length();i++){
        
                dp[i][0] = 0;
            }
            for(int i = 0;i < text2.length();i++){
        
                dp[0][i] = 0;
            }
            for(int i = 1;i <= text1.length();i++){
        
                for(int j = 1;j <= text2.length();j++){
        
                    if(text1.charAt(i - 1) == text2.charAt(j - 1)){
        
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }else{
        
                        // 如果不等的话，要么text1移动一位，要么text2移动一位
                        dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
                    }
                }
            }
            return dp[text1.length()][text2.length()];
        }

### 5.2[回文子串][Link 21] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 19]

状态定义：

boolean[][] dp[i][j]：从第i个字符到第j个字符的字符串是否是回文串

状态方程：

if chars[i] == chars[j] && (j - i <= 2 || dp[i + 1][j - 1])
    	res++;
    	dp[i][j] = true

实现：

public int countSubstrings(String s) {
        
            // dp[i]：对于长度为i的字符串，回文子串的数量
            boolean[][] dp = new boolean[s.length() + 1][s.length() + 1];
            // 初始化，每一个字符都是一个回文子串
            int res = 0;
            int n = s.length();
            char[] charArr = s.toCharArray();
            for (int i = n - 1; i >= 0; i--) {
        
                for (int j = i; j < n; j++) {
        
                    //j-i = {0,1,2}代表一个,两个,三个,字符时 此时可以根据charArr[i] == charArr[j]
                    //得到s[i..j]必定回文
                    if (charArr[i] == charArr[j] && (j - i <= 2 || dp[i + 1][j - 1])) {
        
                        dp[i][j] = true;
                        res++;
                    }
                }
            }
            return res;
        }

### 5.3[最长回文子串][Link 22] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 20]

状态定义：

boolean[][] dp[i][j]：从第i个字符到第j个字符的字符串是否是回文串

状态方程：

if chars[i] == chars[j] && (j - i <= 2 || dp[i + 1][j - 1])
    	res++;
    	dp[i][j] = true
    	s = s.substring(i,j + 1)

实现：

public String longestPalindrome(String s) {
        
            String res = "";
            int len = 0;
            boolean[][] dp = new boolean[s.length() + 1][s.length() + 1];
            for(int i = s.length() - 1;i >= 0;i--){
        
                for(int j = i;j < s.length();j++){
        
                    if(s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
        
                        dp[i][j] = true;
                        if (j - i + 1 > len) {
        
                            len = Math.max(len, j - i + 1);
                            res = s.substring(i,j + 1);
                        }
                    }else{
        
                        dp[i][j] = false;
                    }
                }
            }
            return res;
        }

### 5.4[最长回文子序列][Link 23] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 21]

状态定义：

dp[i][j]：从第i个字符到第j个字符的最长回文子序列的长度是多少

状态方程：

f[i][j] = f[i + 1][j - 1] + 2;// 如果是回文子序列
    f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);// 如果不是回文子序列

实现：

public int longestPalindromeSubseq(String s) {
        
            int n = s.length();
            // f[i][j] 表示 s 的第 i 个字符到第 j 个字符组成的子串中，最长的回文序列长度是多少。
            int[][] f = new int[n][n];
            for (int i = n - 1; i >= 0; i--) {
        
                f[i][i] = 1;
                for (int j = i + 1; j < n; j++) {
        
                    if (s.charAt(i) == s.charAt(j)) {
        
                        f[i][j] = f[i + 1][j - 1] + 2;
                    } else {
        
                        f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                    }
                }
            }
            return f[0][n - 1];
        }

### 5.5[编辑距离][Link 24] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 22]

状态定义：

dp[i][j]：长度为i的字符串转为长度为j的字符串所需的最少操作数

状态方程：

dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);

实现：

public int minDistance(String word1, String word2) {
        
            int[][] dp = new int[word1.length() + 1][word2.length() + 1];
            for(int i = 0;i <= word1.length();i++){
        
                dp[i][0] = i;
            }
            for(int i = 0;i <= word2.length();i++){
        
                dp[0][i] = i;
            }
            for(int i = 1;i <= word1.length();i++){
        
                for(int j = 1;j <= word2.length();j++){
        
                    if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
        
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
        
                        dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
                    }            }
            }
            return dp[word1.length()][word2.length()];
        }

## 六，决定问题 ##

### 6.1[打家劫舍][Link 25] ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70_pic_center][]

状态定义：

偷窃第 k 间房屋，那么就不能偷窃第 k-1 间房屋，偷窃总金额为前 k-2 间房屋的最高总金额与第 k 间房屋的金额之和。
    
    不偷窃第 k 间房屋，偷窃总金额为前 k-1 间房屋的最高总金额。
    
    dp[k] = Math.max(dp[k - 1],dp[k - 2] + nums[k])

实现：

public int rob(int[] nums) {
        
            if(nums.length == 0){
        
                return 0;
            }
            if(nums.length == 1){
        
                return nums[0];
            }
            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            dp[1] = Math.max(nums[0],nums[1]);
            for(int i = 2;i < nums.length;i++){
        
                dp[i] = Math.max(dp[i - 1],dp[i - 2] + nums[i]);
            }
            return dp[nums.length - 1];
        }

### 6.2[打家劫舍 II][II 2] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70_pic_center 1]

状态：

res = Math.max(从第1间偷到第i-1间，从第2间偷到第i间)

实现：

public int rob(int[] nums) {
        
            if(nums.length == 0) return 0;
            if(nums.length == 1) return nums[0];
            return Math.max(tryRob(Arrays.copyOfRange(nums, 0, nums.length - 1)),
                    tryRob(Arrays.copyOfRange(nums, 1, nums.length)));
        }
    
    
        public int tryRob(int[] nums) {
        
            if(nums.length == 0){
        
                return 0;
            }
            int[] dp =new int[nums.length + 1];
            dp[0] = 0;
            dp[1] = nums[0];
            for(int i = 2;i <= nums.length;i++){
        
                //状态转移方程：dp[i] = max{dp[i-1],dp[i-2]+nums[i-1]}
                dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i-1]);
            }
            return dp[nums.length];
        }

### 6.3[打家劫舍 III][III] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70_pic_center 2]

递归实现：

public int rob(TreeNode root) {
        
            return tryRob(root);
        }
    
        /**
         * 以root为根节点返回偷取的最大值
         * @param root
         * @return
         */
        private int tryRob(TreeNode root){
        
            if(root == null){
        
                return 0;
            }
            // 偷取root节点
            int res = 0;
            res += root.val;
            if(root.left != null){
        
                res += tryRob(root.left.left) + tryRob(root.left.right);
            }
            if(root.right != null){
        
                res += tryRob(root.right.left) + tryRob(root.right.right);
            }
            // 不偷root节点
            int resWithoutRoot = tryRob(root.left) + tryRob(root.right);
            return Math.max(resWithoutRoot,res);
        }

[Link 1]: https://leetcode-cn.com/problems/min-cost-climbing-stairs/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70]: /images/20221119/e50caa4d15e040b583119eaeb4e111c0.png
[Link 2]: https://leetcode-cn.com/problems/minimum-path-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200716010848475.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 3]: https://leetcode-cn.com/problems/coin-change/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200716130045706.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 4]: https://leetcode-cn.com/problems/minimum-falling-path-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200716153022146.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 5]: https://leetcode-cn.com/problems/minimum-cost-for-tickets/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200716154829847.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 6]: https://leetcode-cn.com/problems/2-keys-keyboard/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200716203742970.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 7]: https://leetcode-cn.com/problems/perfect-squares/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/202007162048575.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 8]: https://leetcode-cn.com/problems/gas-station/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200719152007676.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 9]: https://leetcode-cn.com/problems/maximal-square/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200719223943496.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[II]: https://leetcode-cn.com/problems/last-stone-weight-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200716210503781.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 10]: https://leetcode-cn.com/problems/ones-and-zeroes/
[Link 11]: https://leetcode-cn.com/problems/climbing-stairs/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200721153624740.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 12]: https://leetcode-cn.com/problems/unique-paths/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20200722011409549.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[II 1]: https://leetcode-cn.com/problems/unique-paths-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20200722012116709.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 13]: https://leetcode-cn.com/problems/target-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/2020072201514585.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 14]: https://leetcode-cn.com/problems/knight-probability-in-chessboard/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 14]: https://img-blog.csdnimg.cn/20200726112102337.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 15]: https://leetcode-cn.com/problems/combination-sum-iv/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 15]: https://img-blog.csdnimg.cn/20200726133728678.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 16]: https://leetcode-cn.com/problems/longest-increasing-subsequence/
[Link 17]: https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/
[Link 18]: https://leetcode-cn.com/problems/minimum-cost-tree-from-leaf-values/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 16]: https://img-blog.csdnimg.cn/2020072910120582.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 19]: https://leetcode-cn.com/problems/unique-binary-search-trees/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 17]: https://img-blog.csdnimg.cn/20200729112207839.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 20]: https://leetcode-cn.com/problems/longest-common-subsequence/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 18]: https://img-blog.csdnimg.cn/20200803193036172.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 21]: https://leetcode-cn.com/problems/palindromic-substrings/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 19]: https://img-blog.csdnimg.cn/20200803194204268.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 22]: https://leetcode-cn.com/problems/longest-palindromic-substring/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 20]: https://img-blog.csdnimg.cn/20200803194907498.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 23]: https://leetcode-cn.com/problems/longest-palindromic-subsequence/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 21]: https://img-blog.csdnimg.cn/20200803195408521.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 24]: https://leetcode-cn.com/problems/edit-distance/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 22]: https://img-blog.csdnimg.cn/2020080319563337.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[Link 25]: https://leetcode-cn.com/problems/house-robber/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200812233858345.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70#pic_center
[II 2]: https://leetcode-cn.com/problems/house-robber-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200812234243730.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70#pic_center
[III]: https://leetcode-cn.com/problems/house-robber-iii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20200813000218553.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70#pic_center