type
status
date
slug
summary
tags
category
icon
password
Last edited time
Jun 2, 2024 08:57 AM
DP问题的基本模式，背包问题，线性DP，状压DP，树形DP，记忆化搜索
0 本节习题总览
01背包习题1: 494. 目标和
01背包习题2: 1049. 最后一块石头的重量 II
完全背包习题: 322. 零钱兑换
方格问题: 120. 三角形最小路径和
最长上升子序列习题: 300. 最长递增子序列
最长公共子序列习题: 1143. 最长公共子序列
编辑距离习题：72. 编辑距离
1 之前的讲解视频
视频开头遗漏的是在讲01背包，也就是给出背包体积为
V，和n个物品，每个物品都有自己的体积和价值，每个物品只能取或不取，最终使得体积之和不超过V的前提下价值最大视频讲解了01背包，完全背包，走方格，最长上升子序列，最长公共子序列，编辑距离问题
2 DP的一些简单的理解
2.1 思考方式
2.2 下标问题
若状态转移方程中有
f[i - 1]这种状态, 下标(状态转移那部分代码)尽量从1开始，否则从0开始2.3 时间复杂度
状态数量(n^几个约束维度) * 转移状态的时间复杂(状态转移代码的时间复杂度)
2.4 其他注意事项
dp的集合划分依据 -> 寻找最后一个不同点 eg. 加不加这个物品到背包, 数字三角形最后一步是由左边还是右边走过来的(根据操作的不同来对集合进行划分)
划分之后的小集合可以递推求出当前集合, 且最小集合已知
3 背包问题
3.1 01背包
3.2 完全背包
3.3 多重背包
3.4 多重背包(二进制优化成01背包)
二进制能表示出全部的数，所以可以把物品分别打包成2的倍数个，枚举的复杂度就变成O(logn)
3.5 分组背包
4 线性DP
5 状压DP
6 记忆化搜索
记忆化搜索，本质还是动态规划，只是实现方式采用了深度优先搜索的形式，但是它不像深度优先搜索那样重复枚举所有情况，而是把已经计算的子问题保存下来，这样就和动态规划的思想不谋而合了。
例题1: 斐波那契数列
例题2: 滑雪
二维数组中找长度最长的下降路线
- 作者:ziuch
- 链接:https://ziuch.com/article/Dynamic-Programming
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。