动态规划入门：从基础概念到实际应用

创作时间:

作者:

@小白创作中心

动态规划入门：从基础概念到实际应用

引用

来源

https://www.bilibili.com/read/mobile?id=33590526

动态规划是一种重要的算法思想，在计算机科学和数学领域有着广泛的应用。本文将从基础概念出发，通过具体问题的分析，帮助读者理解动态规划的核心思想和解题方法。

动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。
动态规划解题思路：

明确状态：确定 dp 数组以及下标的含义
确定 状态转移方程 ：用于描述不同状态之间的关系
dp 数组如何 初始化 ：即，初始状态
确定 转移方向 ：转移方向描述的是推导出不同状态的解的先后关系
举例推导 dp 数组
根据4，主要是采用递推还是递归的思想，递推是前往后推，递归是从后往前推。

①矩阵最大路径和

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

思路：递推的思想，每个点f[i][j] 都是由正上方 f[i-1] [j] 或者左方f[i][ j-1] 中走过来，所以每个点都取其中的最优值，那么遍历到f[4][4]时，自然就是题目最优解。
上图用到占位的思想，这样推导f[1][1]时就不需要特判,不会发生越界。
递推写法
递归写法
因为大多数情况下，递归会计算重复的点，所以递推的写法比递归的写法运行速度更快。

②背包问题

单物品问题

有一个物品大小为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背包问题只有单个，所以比较的是上一行放下和不放下的区别，不能再考虑本行。
01背包问题

完全背包问题

有N种物品和一个容量为V的背包，每种物品都有无限件可用。放入第i种物品的耗费的空间是vi，得到的价值是wi。求解：将哪些物品装入背包，可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。
解析：无限个物品，所以每次放下该物品应该考虑的是本行腾出空间的最优解。
完全背包问题

优化（维度）

可以看到上面的二维数组dp，每次推出dp[ i ] [ j ] 时，就和上一行，或者本行比较，其他行数并没有作用，把上面的二维数组压缩成一维数组存储即可。
维度优化
完全背包问题：因为是刷新，所以dp[ j ]本来存储的值就是上一次物品运算的最优解。d[j -w[i]]肯定是刷新过的，也就是考虑了该好物品的情况。
完全背包维度优化
01背包问题：因为是刷新，所以不能从前往后推，要后往前推，这时dp[j -w[i]] 的值还没刷新，所以比较的是上一个物品的最优解。
01背包问题