小白学习动态规划：入门篇

骑猪看日落 2021-05-12 11:49 577阅读 0赞

# 入门动态规划个人总结 #

## 一、动态规划概念 ##

### 1. 什么是动态规划 ###

动态规划应用于拥有以下特点的问题：一般需要使用动态规划时，该问题的解可以由更小的解得出，例如：当求单位为n的最优解时，可以转换为求第n-1个单位的最优解······也就是说问题的解可以根据子问题的解求出。

### 2. 动态规划问题的特点 ###

① 问题具有**最优子结构性质**。

> 如果问题的最优解所包含的子问题的解也是最优的，那么该问题具有最优子结构

② **无后效性**。

> 简单理解：某个子问题的解一旦确定则不会被改变，求其它子问题的解时仅会使用到这些已经确定好的解

### 3.动态规划的一般思路 ###

① 将原问题分解为子问题

> 把原问题分解为若干个子问题，子问题的规模比原问题更小，但求解的形式是相似的。
> 
> 子问题的解一旦求出就会被保存，所以每个子问题的解仅需求解一次

② 确定状态并确定数组（数组维度和长度）

> 我们往往将子问题的解称为一种“状态”，这种状态的维度一般在确定状态后就可以马上得出，如果这里你不理解没有关系，可以看下面的例题，很好理解~

③ 确定初始（边界）状态的值

> 随着子问题的不断拆分，最终会到达边界，而边界值是可以直接得出的，称为动态规划的初始值或边界值；

④ 确定状态转移方程（递推公式）

> 这一步是最重要的！它决定我们能否解决实际问题
> 
> 找出不同状态之间（前一个子问题与后一个子问题）的关联关系，如何根据之前的状态求出后一个状态，这也可以理解成递推公式

例子：

斐波那契数列求第n项的递推公式：  
 d p \[ n \] \{ d p \[ n − 1 \] + d p \[ n − 2 \] , i f   n > 2 d p \[ 1 \] = d p \[ 0 \] = 1 , i f   n = 1 ∥ n = 0 dp\[n\] \\begin\{cases\} dp\[n-1\]+dp\[n-2\], &if\\ n>2 \\\\ dp\[1\] = dp\[0\] = 1, &if\\ n=1 \\| n=0 \\\\ \\end\{cases\} dp\[n\]\{ dp\[n−1\]\+dp\[n−2\],dp\[1\]=dp\[0\]=1,if n>2if n=1∥n=0  
（可选）⑤ 考虑特殊状态

> 有些特殊状态并不是适用于状态转移方程中的情况，需要另外拿出来单独考虑并更新状态转移方程，在下面的例题中会遇到这个步骤~

⑥ 编码实现

**还是不太懂或者很复杂？没关系，结合题目看看就明白了~在你掌握了入门方法后，这六个步骤就会了如指掌**

## 二、入门例题讲解 ##

### 类型一、一维dp数组 ###

LeetCode70. 爬楼梯

> 问题描述：假设你需要爬楼梯，需要爬n阶才能到达楼顶，每次可以爬1或2阶，由多少种不同的方法可以爬到楼顶？

① 将原问题分解为子问题

> 假设n = 5，求爬上第5阶楼梯的最多方法，必定要求出第4阶的最多方法，求第4阶的最多方法，必定要求出第3阶的最多方法······最终求爬上第1阶的最多方法

② 确定状态并确定数组

> 每一个阶梯都对应一个状态，该状态表示爬上该楼梯的最多方法数值，所以数组维度为1，数组长度为n

③ 边界状态

> 爬上第1阶楼梯的方法数为1，即爬1阶；
> 
> 爬上第2阶楼梯的方法数为2，每次爬1阶要爬2次或每次爬2阶爬1次

④ 确定状态转移方程

> **如何找规律？**
> 
> 手算（少用）：列出前面较为容易计算的例子，手写出所有情况，再从中找规律得到状态转移方程。
> 
> 假设n = 5，则经过**手算**可以得到如下表格
> 
> <table> 
>  <thead> 
>   <tr> 
>    <th>阶梯数</th> 
>    <th>1</th> 
>    <th>2</th> 
>    <th>3</th> 
>    <th>4</th> 
>    <th>5</th> 
>   </tr> 
>  </thead> 
>  <tbody> 
>   <tr> 
>    <td>方法数</td> 
>    <td>1</td> 
>    <td>2</td> 
>    <td>3</td> 
>    <td>5</td> 
>    <td>8</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> 思想（多用）：第n阶可以从第(n-2)阶跨上来或第(n-1)阶爬上来，显然，到达第n阶楼梯的最多方法数等于爬第(n-2)阶的最多方法数加上第(n-1)阶的最多方法数

d p \[ n \] \{ d p \[ n − 1 \] + d p \[ n − 2 \] , i f   n ≥ 2 d p \[ 0 \] = 1 , i f   n = 0 d p \[ 1 \] = 2 , i f   n = 1 dp\[n\]\\begin\{cases\}dp\[n-1\]+dp\[n-2\], &if\\ n≥2\\\\ dp\[0\] = 1, &if\\ n=0 \\\\ dp\[1\] = 2, &if\\ n=1 \\end\{cases\} dp\[n\]⎩⎪⎨⎪⎧dp\[n−1\]\+dp\[n−2\],dp\[0\]=1,dp\[1\]=2,if n≥2if n=0if n=1

> 注意我这里定义的dp数组的下标0位置对应爬上第1阶楼梯的最多方法数而不是第0阶！

⑥ 编码实现

class Solution { 
        public int climbStairs(int n) { 
    		int[] maxSum = new int[n];
    		for (int i = 0; i < maxSum.length; i++) { 
                if(i == 0){  //第1阶
    				maxSum[i] = 1;
    			}else if(i == 1){  //第2阶
    				maxSum[i] = 2;
    			}else{  //第3阶及以上
    				maxSum[i] = maxSum[i-1]+maxSum[i-2];
    			}
    		}
    	    return maxSum[n-1];
        }
    }

### 类型二、二维dp数组 ###

LeetCode62. 不同路径

> 问题描述：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
> 
> 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
> 
> 问总共有多少条不同的路径？

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

> **说明**：m 和 *n* 的值均不超过 100。

① 将原问题拆分为子问题

> 根据题意：机器人每次只能向下或向右走一步，求走到 \[i, j\] 位置的最多路径解有两种形式：
> 
> （上面格子）\[i-1,j\] 向下走一步到达\[i, j\]
> 
> （左边格子）\[i, j-1\]向右走一步到达\[i, j\]
> 
> 所以转化为求\[i-1, j\]和\[i, j-1\]的最多路径解······

② 确定状态并确定数组

> 每个格子都有到达自己的最多路径，所以每个到达每个格子的最多路径就是一个状态。
> 
> 数组：由于格子拥有二维空间（坐标x，坐标y），需要用二维数组存储每个格子的最多路径数，\[i,j\]代表第i行第j列的格子，dp\[i\]\[j\]代表到达该格子的最多路径

③边界状态

> 站在原地有一种走法，就是在原地，所以dp\[0\]\[0\] = 1；
> 
> 向右走第一步有一种走法，dp\[0\]\[1\] = 1 (if m > 1 && n > 1)
> 
> 向下走第一步有一种走法，dp\[1\]\[0\] = 1 (if m > 1 && n > 1)

④ 确定状态转移方程

> 机器人每次可以向右走一步或向下走一步，所以走到第\[i, j\]格子的最多路径就是可以到达它的所有路径之和  
>  d p \[ i \] \[ j \] = d p \[ i − 1 \] \[ j \] + d p \[ i \] \[ j − 1 \] dp\[i\]\[j\] = dp\[i-1\]\[j\] + dp\[i\]\[j-1\] dp\[i\]\[j\]=dp\[i−1\]\[j\]\+dp\[i\]\[j−1\]

所以可以初步得到状态转移方程：  
 d p \[ i \] \[ j \] \{ d p \[ i − 1 \] \[ j \] + d p \[ i \] \[ j − 1 \] , i f   j ≥ 1   A N D   i > = 1 1 , i f   ( i = 0 A N D j = 0 ) O R ( i = 0   A N D   j = 1 ) O R ( i = 1   A N D   j = 0 ) dp\[i\]\[j\]\\begin\{cases\}dp\[i-1\]\[j\]+dp\[i\]\[j-1\], &if\\ j≥1\\ AND\\ i>=1\\\\ 1, &if\\ (i=0ANDj=0)OR(i=0\\ AND\\ j=1)OR(i=1\\ AND\\ j=0)\\\\ \\end\{cases\} dp\[i\]\[j\]\{ dp\[i−1\]\[j\]\+dp\[i\]\[j−1\],1,if j≥1 AND i>=1if (i=0ANDj=0)OR(i=0 AND j=1)OR(i=1 AND j=0)  
⑤ 考虑特殊状态

> 第一行和第一列的所有格子的最多路径都只有1种路径
> 
> 第一行的格子只能由起点向右走
> 
> 第一列的格子只能由起点向下走

所以需要更新状态转移方程  
 d p \[ i \] \[ j \] \{ d p \[ i − 1 \] \[ j \] + d p \[ i \] \[ j − 1 \] , i f   j ≥ 1   A N D   i ≥ 1 1 , i f   ( i = 0   A N D   j ≥ 0 ) O R ( i ≥ 0   A N D   j = 0 ) dp\[i\]\[j\]\\begin\{cases\}dp\[i-1\]\[j\]+dp\[i\]\[j-1\], &if\\ j≥1\\ AND\\ i≥1\\\\ 1, &if\\ (i=0\\ AND\\ j≥0)OR(i≥0\\ AND\\ j=0)\\\\ \\end\{cases\} dp\[i\]\[j\]\{ dp\[i−1\]\[j\]\+dp\[i\]\[j−1\],1,if j≥1 AND i≥1if (i=0 AND j≥0)OR(i≥0 AND j=0)  
⑥ 编码实现

package leetcode.动态规划.中等.不同路径;
    
    /** * @author Zeng * @date 2020/1/20 9:34 */
    public class Solution { 
    
        public static int uniquePaths(int m, int n) { 
    
            int[][] dp = new int[m][n];
            for (int i = 0; i < m; i++){ 
                for (int j = 0; j < n; j++){ 
                    //上边界
                    if(i == 0 && j >= 0){ dp[i][j] = 1;continue;}
                    //左边界
                    if(j == 0 && i >= 0){ dp[i][j] = 1;continue;}
                    //其它情况
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
            return dp[m-1][n-1];
        }
    
        public static void main(String[] args) { 
            int i = uniquePaths(7, 3);
            System.out.println("最多路径："+i);
        }
        
    }
    /** * 最多路径：28 */

**注意事项：**

> 如果只有一个格子，即(m, n) = (1, 1) ，那么起点就等于终点，也就是一种路径

![在这里插入图片描述][20200202222417232.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk0OTMyOA_size_16_color_FFFFFF_t_70]: /images/20210511/70526b9f876547a8964b9888f96e65f9.png
[20200202222417232.png]: /images/20210511/60fe0ad2d9fe46858dca690318f7a877.png