- 1
dp动态规划
（应 这个可以有 讲解）
注：此文内容以作者本人观点+网上参考资料为主，如有问题可及时提出
动态规划可以理解作递推的一种，只不过动态规划（以后简称dp或动归）
大多数时候可以简化为三步骤：
1.设计状态
这一步通过字面意思，可以理解为：为一个你想要求的答案准备一个状态来表示它。
在这里解释不太清楚，请访问如下题目：https://www.luogu.com.cn/problem/P1048
或简化题面：给定n个物品，给了一个时间T，然后每个物品都给出一个价值和选择所需的时间t（每个物品仅能选一次，也可不选），求在不超过时间T的情况下最多可以获得的价值
此题状态即可设为dp[i][j],表示在前i个物品中选择了总时长不超过j的最大价值
状态设计好就是关键，但状态往往需要进行优化，比如这道题，因为第i个物品选择仅可能与i-1所处状态（即dp[i]与dp[i-1]）有关，也就是第i-2位就没有用处了，即可试图压缩第一维i，此处不多讲解，之后再说。
2.状态转移方程
状态转移方程就是根据状态转移过来，即根据一个已知状态推导出下一个状态。
比如还是上文这道题，状态转移方程为：
dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+v[i])
其中i为物品编号，j为时间，t[i]为第i个物品所需时间，v[i]为第i个物品价值
可以简单理解，在max中（默认你会部分基础，所以不多讲述一些基础知识，但可以发出询问）
第一项即可理解为不做选择（即不选择第i个物品）
第二项理解为做选择（即选择第i个物品），代价是t[i]，但价值为v[i]，需要寻找上一行状态预留t[i]的时间的最大价值再加上当前状态
3.初始化和求解
初始化中，需要考虑你的状态方程是如何设计，然后在没有任何状态下的初始值
比如这道题，因为在不做选择时价值为0，所以应初始化：
dp[0][0]=0;
但是对于dp其他的状态，需要根据转移方程来进行初始化，比如：
dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+v[i])
因为要取max，所以多用极大值来初始化，不多讲解
求解中，考虑题意中要求的状态是哪个，这道题就是满状态，即
dp[n][T]
其他题可能因题而异，甚至可能还会有求和、最大值等，不多讲解
动归主体就是这些内容，但是动归可不止这些，在普通动归的前提下延伸出很多，比如和图论结合形成树形dp等，这些之后有想了解者可以问问。
感谢观看
llwf 2025.05.30
尾注：端午假期快乐!
（排版如果不合适可以提出，下次修正）
