动态规划：基本概念以及面试常见题型

淩亂°似流年 2022-11-09 01:27 203阅读 0赞

### 动态规划入门 ###

*   *  动态规划基本概念
     *   *  数字三角形
         *  动规四要素
         *  动态规划的使用场景与题型分类
     *  简单例题
     *   *  LeetCode 62.不同路径
         *  LeetCode 63.不同路径ll
         *  LeetCode 55. 跳跃游戏

动态规划问题详解：  
[一篇文章带你解决最常见的动态规划 --> 01背包][--_ 01]

> 动态规划 Dynamic Programming 简称动规或者DP  
> 是一种算法思想，而不是一种具体的算法

## 动态规划基本概念 ##

**动态规划的算法思想**  
大规模问题的依赖于小规模问题的计算结果，类似思想算法的还有:递归，分治法。

**使用前提**  
无后效性，当前的决策不会影响后面的决策。

**动态规划 DP与贪心算法Greedy的区别**

<table> 
 <thead> 
  <tr> 
   <th>动态规划</th> 
   <th>贪心算法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>为了长远的利益会损失当前利益</td> 
   <td>永远追求当前利益最大化</td> 
  </tr> 
 </tbody> 
</table>

动态规划的两种实现方法

1.  记忆化搜索 (使用递归实现)
2.  多重循环 (使用for循环实现)

按惯例，先来一道例题带大家了解动态规划的两种实现方法：

### 数字三角形 ###

描述  
给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU1MjIxMjM5_size_16_color_FFFFFF_t_70]

1.记忆化搜索

//Version 1 : Memorize Search
    public class Solution { 
        private int n;
        private int[][] minSum;
        private int[][] triangle;
    
        private int search(int x, int y) { 
            if (x >= n) { 
                return 0;
            }
    
            if (minSum[x][y] != Integer.MAX_VALUE) { 
                return minSum[x][y];
            }
    
            minSum[x][y] = Math.min(search(x + 1, y), search(x + 1, y + 1))
                + triangle[x][y];
            return minSum[x][y];
        }
    
        public int minimumTotal(int[][] triangle) { 
            if (triangle == null || triangle.length == 0) { 
                return -1;
            }
            if (triangle[0] == null || triangle[0].length == 0) { 
                return -1;
            }
            
            this.n = triangle.length;
            this.triangle = triangle;
            this.minSum = new int[n][n];
    
            for (int i = 0; i < n; i++) { 
                for (int j = 0; j < n; j++) { 
                    minSum[i][j] = Integer.MAX_VALUE;
                }
            }
    
            return search(0, 0);
        }
    }

2.for循环

//Version 1: Bottom-Up 自底向上
    public class Solution { 
        /** * @param triangle: a list of lists of integers. * @return: An integer, minimum path sum. */
        public int minimumTotal(int[][] triangle) { 
            if (triangle == null || triangle.length == 0) { 
                return -1;
            }
            if (triangle[0] == null || triangle[0].length == 0) { 
                return -1;
            }
            
            // state: f[x][y] 代表从i, j 走到最底层的最短路径值
            int n = triangle.length;
            int[][] f = new int[n][n];
            
            // initialize： 初始化重点 -最后一层
            for (int i = 0; i < n; i++) { 
                f[n - 1][i] = triangle[n - 1][i];
            }
            
            // bottom up
            //function: 从下往上倒过来推导，计算每个坐标到哪
            for (int i = n - 2; i >= 0; i--) { 
                for (int j = 0; j <= i; j++) { 
                    f[i][j] = Math.min(f[i + 1][j], f[i + 1][j + 1]) + triangle[i][j];
                }
            }
            
            // answer 起点就是答案
            return f[0][0];
        }
    }
    
    // version 2: top-down 自顶向下
    public class Solution { 
        /** * @param triangle: a list of lists of integers. * @return: An integer, minimum path sum. */
        public int minimumTotal(int[][] triangle) { 
            if (triangle == null || triangle.length == 0) { 
                return -1;
            }
            if (triangle[0] == null || triangle[0].length == 0) { 
                return -1;
            }
            
            // state: f[x][y] 代表从0，0 走到 i, j的最短路径值
            int n = triangle.length;
            int[][] f = new int[n][n];
            
            // initialize: 三角形的左边和右边要初始化
            // 因为他们分别没有左上角和右上角的点
            f[0][0] = triangle[0][0];
            for (int i = 1; i < n; i++) { 
                f[i][0] = f[i - 1][0] + triangle[i][0];
                f[i][i] = f[i - 1][i - 1] + triangle[i][i];
            }
            
            // function: f[i][j] = Math.min(f[i - 1][j], f[i - 1][j - 1]) + triangle[i][j];
            //i, j 这个位置是从 i - 1， 或者 i - 1, j - 1走过来的 
            for (int i = 1; i < n; i++) { 
                for (int j = 1; j < i; j++) { 
                    f[i][j] = Math.min(f[i - 1][j], f[i - 1][j - 1]) + triangle[i][j];
                }
            }
            
            // answer: 最后一层的任意位置都可以是路径的终点
            int best = f[n - 1][0];
            for (int i = 1; i < n; i++) { 
                best = Math.min(best, f[n - 1][i]);
            }
            return best;
        }
    }

### 动规四要素 ###

动规的状态 State —— 递归的定义

*  用 f\[i\] 或者 f\[i\]\[j\] 代表在某些特定条件下某个规模更小的问题的答案
 *  规模更小用参数 i,j 之类的来划定

动规的方程 Function —— 递归的拆解

*  大问题如何拆解为小问题
 *  f\[i\]\[j\] = 通过规模更小的一些状态求 max / min / sum / or 来进行推导

动规的初始化 Initialize —— 递归的出口

*  设定无法再拆解的极限小的状态下的值
 *  如 f\[i\]\[0\] 或者 f\[0\]\[i\]

动规的答案 Answer —— 递归的调用 - 最后要求的答案是什么

*  如 f\[n\]\[m\] 或者 max(f\[n\]\[0\], f\[n\]\[1\] … f\[n\]\[m\])

### 动态规划的使用场景与题型分类 ###

使用场景  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU1MjIxMjM5_size_16_color_FFFFFF_t_70 1]  
**三种适用动规的场景**  
• 求最值  
• dp\[\] 的值的类型是最优值的类型  
• dp\[大问题\] = max\{dp\[小问题1\], dp\[小问题2\], …\}  
• dp\[大问题\] = min\{dp\[小问题1\], dp\[小问题2\], …\}

**• 求方案数**  
• dp\[\] 的值的类型是方案数(整数)  
• dp\[大问题\] = ∑(dp\[小问题1\], dp\[小问题2\], …)  
• ∑=sum

**• 求可行性**  
• dp\[\] 的值是 true / false  
• dp\[大问题\] = dp\[小问题1\] or dp\[小问题2\] or …  
• 代码通常用 for 小问题 if dp\[小问题\] == true then break 的形式实现

**不适用动态规划的场景：**

1.  求出所有具体的方案  
    只求出一个具体方案可以动态规划  
    该判断标准成功率 99 %
2.  输入的数据是无序的  
    除了背包问题
3.  暴力算法的复杂度已经是多项式级别  
    动态规划擅长与优化指数复杂度（2n,n!) 到多项式级别 （n 2,n3) ，不擅长优化n3到n2

**动态规划的题型**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU1MjIxMjM5_size_16_color_FFFFFF_t_70 2]

动态规划的题型分类有什么用?

> 不同题型的动态规划对一个的状态表示方法是不同的，因此如果成功的找对了题型，就能够解决 DP 最难的状态表示问题。

1.  **坐标型动态规划**  
    dp\[i\] 表示从起点到坐标 i 的最优值/方案数/可行性  
    dp\[i\]\[j\] 表示从起点到坐标 i,j 的最优值/方案数/可行性  
    代表题: Triangle, Unique Paths
2.  **前缀型之划分型**  
    dp\[i\] 表示前 i 个字符的最优值/方案数/可行性  
    dp\[i\]\[j\] 表示前 i 个字符划分为 j 个部分的最值/方案数/可行性  
    代表题: Word Break, Word Break III
3.  **前缀型之匹配型**  
    dp\[i\]\[j\] 表示第一个字符串的前 i 个字符匹配上第二个字符串 的前 j 个字符的最优值/方案数/可行性  
    代表题: Longest Common Subsequence, Wildcard Matching
4.  区间型  
    dp\[i\]\[j\] 表示区间 i~j 的最优值/方案数/可行性  
    代表题: Stone Game, Burst Balloons
5.  **背包型**  
    dp\[i\]\[j\] 表示前 i 个物品里选出一些物品组成和为 j 的大小的最优 值/方案数/可行性  
    代表题: Backpack 系列

## 简单例题 ##

### LeetCode 62.不同路径 ###

[LeetCode 62.不同路径][LeetCode 62.]

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

class Solution { 
        public int uniquePaths(int m, int n) { 
            //state: d[i][j] 代表 0,0 走到 i,j 的方案数
            int[][] dp = new int[m][n];
    
            //initalize:
            for(int i = 0; i < m; i++){ 
                dp[i][0] = 1;
            }
            for(int j = 0; j < n; j++){ 
                dp[0][j] = 1;
            }
    
            //function:
            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];
                }
            }
    
            //answer
            return dp[m-1][n-1];
        }
    }

### LeetCode 63.不同路径ll ###

[LeetCode 63.不同路径ll][LeetCode 63._ll]

题目说明：  
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

public class Solution { 
        /** * @param obstacleGrid: A list of lists of integers * @return: An integer */
        public int uniquePathsWithObstacles(int[][] obstacleGrid) { 
            // write your code here
            if(obstacleGrid == null || obstacleGrid.length == 0){ 
                return 0;
            }
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            int[][] dp = new int[m][n];
            
            //
            for(int i = 0; i < m; i++){ 
                if(obstacleGrid[i][0] == 1){ 
                    break;
                }
                dp[i][0] = 1;
            }
            
            for(int j = 0; j < n; j++){ 
                if(obstacleGrid[0][j] == 1){ 
                    break;
                }
                dp[0][j] = 1;
            }
            
            for(int i = 1; i < m; i++){ 
                for(int j = 1; j < n; j++){ 
                    if(obstacleGrid[i][j] == 1){ 
                        continue;
                    }
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
            return dp[m-1][n-1];
        }
        
    }

### LeetCode 55. 跳跃游戏 ###

[LeetCode 55. 跳跃游戏][LeetCode 55.]

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

class Solution { 
        public boolean canJump(int[] nums) { 
            if(nums == null || nums.length == 0){ 
                return false;
            }
            //state: dp[i] 代表是否能够跳到坐标i
            boolean[] dp = new boolean[nums.length];
    
            //initialization: 0 是初始站位
            dp[0] = true;
    
            //function:
            for(int i = 1; i < nums.length; i++){ 
                for(int j = 0; j < i; j++){ 
                    if(dp[j] && nums[j] + j >= i){ 
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[nums.length - 1];
        }
    }

骑士的最短路径II  
描述  
在一个 n \* m 的棋盘中(二维矩阵中 0 表示空 1 表示有障碍物)，骑士的初始位置是 (0, 0) ，他想要达到 (n - 1, m - 1) 这个位置，骑士只能从左边走到右边。找出骑士到目标位置所需要走的最短路径并返回其长度，如果骑士无法达到则返回 -1.

public class Solution { 
        /** * @param grid: a chessboard included 0 and 1 * @return: the shortest path */
        public static int[] deltaX = { 1, -1, 2, -2};
        public static int[] deltaY = { -2, -2, -1, -1};
        
        public int shortestPath2(boolean[][] grid) { 
            // write your code here
            if(grid == null || grid.length == 0){ 
                return -1;
            }
            
            int n = grid.length, m = grid[0].length;
            
            //state: dp[i][j] 表示从0,0 到 i,j 的最短距离
            int[][] dp = new int[n][m];
            
            //initialization: 0,0
            //其他点用Max_VALUE代表暂时无法达到
            for(int i = 0; i < n; i++){ 
                for(int j = 0; j < m; j++){ 
                    dp[i][j] = Integer.MAX_VALUE;
                }
            }
            dp[0][0] = 0;
            
            for(int j = 0; j < m; j++){ 
                for(int i = 0; i < n; i++){ 
                    if(grid[i][j]){ 
                        continue;
                    }
                    
                    for(int direction = 0; direction < 4; direction++){ 
                        int x = i + deltaX[direction];
                        int y = j + deltaY[direction];
                        if(x < 0 || x >= n || y < 0 || y >= m){ 
                            continue;
                        }
                        if(dp[x][y] == Integer.MAX_VALUE){ 
                            continue;
                        }
                        dp[i][j] = Math.min(dp[i][j], dp[x][y] + 1);
                    }
                }
            }
            if(dp[n-1][m-1] == Integer.MAX_VALUE){ 
                return -1;
            }
            return dp[n-1][m-1];
        }
    }

[--_ 01]: https://blog.csdn.net/m0_55221239/article/details/114800395?spm=1001.2014.3001.5501
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU1MjIxMjM5_size_16_color_FFFFFF_t_70]: /images/20221023/e03bb0982ecc42a8b565364655268008.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU1MjIxMjM5_size_16_color_FFFFFF_t_70 1]: /images/20221023/338139e3e0f5413b90e1fa7c14e69f95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU1MjIxMjM5_size_16_color_FFFFFF_t_70 2]: /images/20221023/a700bbf5963043a88d3c425cfccd5a56.png
[LeetCode 62.]: https://leetcode-cn.com/problems/unique-paths/
[LeetCode 63._ll]: https://leetcode-cn.com/problems/unique-paths-ii/
[LeetCode 55.]: https://leetcode-cn.com/problems/jump-game/