动态规划入门：从基础概念到经典问题解析

动态规划入门：从基础概念到经典问题解析

动态规划是一种通过拆分子问题、记住过往计算结果来减少重复计算的算法思想。本文将从基本概念出发，通过具体实例，深入浅出地讲解动态规划的核心思想和解题步骤，帮助读者掌握这一重要的算法技巧。

动态规划的基本思路

动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。动态规划解题通常遵循以下步骤：

1. 明确状态：确定 dp 数组以及下标的含义
2. 确定状态转移方程：用于描述不同状态之间的关系
3. dp 数组初始化：即，初始状态
4. 确定转移方向：描述推导出不同状态的解的先后关系
5. 举例推导 dp 数组：根据转移方向，采用递推或递归的思想

典型问题解析

①矩阵最大路径和

有如下矩阵，从A点走到B点，每次只能往右走和往下走，问走过的路径最大和是多少？

思路：递推的思想，每个点f[i][j] 都是由正上方 f[i-1] [j] 或者 左方f[i][ j-1] 中走过来，所以每个点都取其中的最优值，那么遍历到f[4][4]时，自然就是题目最优解。

递推写法：

递归写法：

因为大多数情况下，递归会计算重复的点，所以递推的写法比递归的写法运行速度更快。

②背包问题

背包问题是动态规划中非常经典的一类问题，下面将通过几个具体的例子来说明。

单物品问题

有一个物品大小为5的物品，背包大小为n，请问剩余的最小空间是？

dp推导：

上图可见，下标 i 代表的是背包容量，从背包容量0开始推导到n，

推导方程为：dp[ i ]=( j>=5? j - 5: j )

单物品无限个问题

有无数个物品大小为3的物品，背包大小为n，请问剩余的最小空间是？

dp推导：

上图可见，下标 i 代表的是背包容量，从背包容量0开始推导到n，

推导方程为：

两个物品无限个问题

有无数个物品大小为2，3的物品，背包大小为n，请问剩余的最小空间是？

对于多个物品，其中下标 j 代表的是背包容量，下标 i 是物品编号，用数组存储。

下标 i 为 0 的代表一个物品都不放的最优解。

下标 i 为 1的横线代表只考虑1号物品，也就是大小为2的物品的最优解。

下标 i 为 2 的代表 考虑 2号物品 的最优解（兼顾 1号物品）。

当 背包容量 j < 3时，2号物品放不下，所以dp[ i ] [ j ] = dp [i-1][ j ] ;

当 背包容量 j >= 3时,就要考虑是否放下3号物品，哪个值更优。不放下就是 dp [i-1][ j ]，然后就是考虑2好物品的情况下腾出空间放下 dp [ i ][ j -3 ] ，j -3 就代表腾出3大小位置后的最优解。

01背包问题

有N件物品和一个容量为V的背包。放入第i件物品耗费的空间是vi，得到的价值是wi。求解将哪些物品装入背包可使价值总和最大。

解析：01背包问题只有单个，所以比较的是上一行 放下和不放下的区别，不能再考虑本行。

完全背包问题

有N种物品和一个容量为V的背包，每种物品都有无限件可用。放入第i种物品的耗费的空间是vi，得到的价值是wi。求解：将哪些物品装入背包，可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

解析：无限个物品，所以每次放下该物品应该考虑的是本行腾出空间的最优解。

优化 （维度）

可以看到上面的二维数组dp，每次推出dp[ i ] [ j ] 时，就和上一行，或者本行比较，其他行数并没有作用，把上面的二维数组压缩成一维数组存储即可。

维度优化

完全背包问题：因为是刷新，所以dp[ j ]本来存储的值就是上一次物品运算的最优解。d[j -w[i]]肯定是刷新过的，也就是考虑了该好物品的情况。

完全背包维度优化

01背包问题：因为是刷新，所以不能从前往后推，要后往前推，这时dp[j -w[i]] 的值还没刷新，所以比较的是上一个物品的最优解。

01背包问题

多重背包

有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

解析：有限个数的物品，拆分成01背包问题。例如1号物品有3个，那么直接添加3次1号物品。

动态规划问题的关键点

动态规划问题关键要考虑的4个点：

1. dp数组的含义（考虑 dp数组元素和下标表示什么含义）
2. 递推公式
3. dp数组的初始化
4. 遍历顺序