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

入门动态规划个人总结

一、动态规划概念

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，则经过手算可以得到如下表格

阶梯数	1	2	3	4	5
方法数	1	2	3	5	8

思想（多用）：第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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

类型二、二维dp数组

LeetCode62. 不同路径

问题描述：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

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

说明：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]格子的最多路径就是可以到达它的所有路径之和
$$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
  */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

注意事项：

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