算法刻意练习之动态规划

我不是女神ヾ 2022-12-21 06:25 167阅读 0赞

## 1 特点 ##

### 1.1 动态规划和递归或者分治没有根本上的区别（关键看有无最优的子结构) ###

**1.共性:找到重复子问题；  
2.差异性:最优子结构、中途可以淘太欠优解**；

### 1.2 递归问题一含有重疊的子问题，操作重复 ###

1.记忆化搜索(自顶而下)；  
**2.动态规划(自底而上)**；

### 1.3 常识 ###

**一般求解最值的问题都可以朝着动态规划的方向去想**。

## 2 关键点： ##

1.根据最优子结构定义状态：dp[n] = bestOf(dp[n-1], dp[n-2], ...)
     2.递推状态转移方程（DP方程）
       一维：dp[i] = dp[n-1] + dp[n-2]
       二维: dp[i,j] = dp[i+1], i] + dp[i][j+1] (且判断dp[i, j]是否空地)
     3.考虑初始化（base case）
     4.考虑输出
     5.考虑优化空间

## 3 DP顺推模板 ##

### 3.1 模板核心 ###

// 模板核心
    for 状态1 in 状态1的所有取值：
        for 状态2 in 状态2的所有取值：
            for ...
                dp[状态1][状态2][...] = 择优(选择1，选择2...)

### 3.2 模板例子 ###

// 模板例子
    public void fun(int level, int param) {
        // base case：定义 dp 数组并初始化第 0 行和第 0 列。// 二维情况
        dp = [][]
    
        // dp：根据状态转移方程 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 进行递推。
        for i = 0..M {
            for j = 0..N {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
            }
        }
        return dp[M][N]
    }

### 3.3 经典案例 ###

// 62. 不同路径
    fun uniquePaths(m: Int, n: Int): Int {
        if (m == 0 || n == 0) return 0
    
        // base case：定义 dp 数组并初始化第 0 行和第 0 列。// 二维情况
        val dp = Array(m) { IntArray(n) }
        for (i in 0 until m) dp[i][0] = 1
        for (j in 0 until n) dp[0][j] = 1
    
        // dp：根据状态转移方程 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 进行递推。
        for (i in 1 until m) {
            for (j in 1 until n) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
            }
        }
        return dp[m - 1][n - 1]
    }

## 4 思路 ##

### 4.1 想到动态规划，但又不知从何入手，可以试试这么思考 ###

**1.大问题是什么？  
2.规模小一点的子问题是什么？  
3.它们之间有什么联系？**

### 4.2 例子：一个字符串是否是回文串？ ###

大问题是一个字符串是否是回文串，那规模小一点的子问题呢？  
答：一个字符串是回文串，它的首尾字符相同，且剩余子串也是一个回文串。所以，剩余子串是否为回文串，就是规模小一点的子问题，它的结果影响大问题的结果。我们怎么去描述子问题呢？写出

（1）base case：只有一个字母的时候肯定是回文子串，for (i in 0 until n) dp[i][i] = true
    （2）db方程：
        // 如果s[i]==s[j]，说明只要dp[i+1][j-1]是回文子串，那么dp[i][j]也是回文子串；如果s[i]!=s[j]，说明dp[i][j]必定不是回文子串。
        if(s.charAt(i) == s.charAt(j)){
            dp[i][j] = dp[i+1][j-1]
        } else {
            dp[i][j] = false;
        }

## 5 经典题目 ##

### 5.1 [爬楼梯][Link 1] ###

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

### 5.2 不同路径 ###

（1）[不同路径1][1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 1]

（2）[不同路径2][2]

### 5.3 [打家劫舍][Link 2] ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 2]  
[213. 打家劫舍 II][213. _ II]

### 5.4 [最小路径和][Link 3] ###

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

### 5.5 买卖股票的最佳时机系列 ###

[买卖股票的最佳时机 1][1 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 6]

## 6 高阶递归问题 ##

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

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

[Link 1]: https://leetcode-cn.com/problems/climbing-stairs/solution/70-pa-lou-ti-by-chen-li-guan/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/dbb42eaa7f7849cf9898f37128dcaa1d.png
[1]: https://leetcode-cn.com/problems/unique-paths/solution/62-bu-tong-lu-jing-by-chen-li-guan/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/8d8db245c47e4010bd458eaa2b9e52fd.png
[2]: https://leetcode-cn.com/problems/unique-paths-ii/solution/63-bu-tong-lu-jing-ii-by-chen-li-guan-2/
[Link 2]: https://leetcode-cn.com/problems/house-robber/solution/198-da-jia-jie-she-by-chen-li-guan/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/5dd0e8b8f68148dab3ad73c110de01ee.png
[213. _ II]: https://leetcode-cn.com/problems/house-robber-ii/solution/213-da-jia-jie-she-ii-by-chen-li-guan/
[Link 3]: https://leetcode-cn.com/problems/minimum-path-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/1b75a940c974452bbd4e62a2a5b515c5.png
[1 1]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-1-by-chen-li/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/3741ff30698445d18c5f1f59592a8265.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221120/b611714a8d7743119ea550a3c9c114f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221120/785fe92c80b44cc9ba2d465b3de4edd3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221120/b036604153d14b71a4b914fd346bff62.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221120/7cf63bb29e654c2eafa6ed3463ea67c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5saWd1YW4_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221120/0592279857ec4bceb5a69fa3cd31c602.png