动态规划（DP）通过拆分问题，定义问题状态和状态转移关系，以递推方式解决具有最优子结构的问题。其核心在于状态定义和状态转移方程的设计，通过记录子问题的解，避免重复计算，从而提高效率。
经典动态规划问题
-
数字三角形: 求从三角形顶点到底部的路径最大数字和。
- 状态定义：
f[i][j]表示从顶点到坐标(i, j)的路径最大和。 - 转移方程：
f[i][j] = max(f[i-1][j], f[i-1][j-1]) + a[i][j]
- 状态定义：
-
最长上升子序列（LIS）: 求序列中最长上升子序列的长度。
- 状态定义：
f[i]表示以第i个元素结尾的最长上升子序列的长度。 - 转移方程：
f[i] = max(f[j] + 1)，其中j < i且a[j] < a[i]
- 状态定义：
-
01 背包问题: 给定物品的体积和价值，在不超过背包容量的情况下，求能装入背包的最大价值。
- 状态定义：
f[i][j]表示考虑前i个物品，背包容量为j时能获得的最大价值。 - 转移方程：
f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])， 其中v[i]和w[i]分别表示第i个物品的体积和价值。
- 状态定义：
动态规划优化
- 时间优化: 利用二分查找等方法优化状态转移过程。
- 空间优化: 使用滚动数组减少空间复杂度。
总结
动态规划通过定义问题状态和状态转移关系，以递推方式解决具有最优子结构的问题，并可以通过时间和空间优化提高算法效率，广泛应用于各个领域。
暂无评论