标签：推导 一遍 问题 一维 最优 递推 dp

前言

马上csp-s考试了，却发现自己dp太菜了，打算恶补dp

线性dp理解

递推/记忆化搜索，有很多种理解方式
递归重叠子问题的记忆化搜索：

像这里例如 \(f[3]\) 可以通过一次计算得到，保存答案，下一次直接调用即可，省去很多复杂度

我们从此引出dp第一个性质：最优子结构
大问题的最优解包含小问题的最优解，并且小问题的最优解可以推导出大问题的最优解

递推：
我们不管dp[i-1]是多少，但可以从dp[i-1]推导得出dp[i]

dp第二个性质：无后效性
未来与过去无关

dp实现方法：

自顶而下：大问题拆解成小问题求解
常用递归+记忆化实现
自底而上：小问题组合成大问题求解
常用制表递推实现
这是最常见的dp方法

背包dp

0/1背包

状态设计

\(dp[i][j]\) 表示只装前i个物品，体积为j时的最大价值

转移方程

\(c[i],v[i]\)表示第i个物品的体积和价值

方式1：

\[dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]) \]

方式2：

\[dp[i+1][j+w[i+1]]=max(dp[i+1][j+w[i+1]],dp[i][j]+v[i+1]) \]

区别：

方式一是通过上一维来推导这一维，方式二是通过这一维推导下一维

标签：推导,一遍,问题,一维,最优,递推,dp
From： https://www.cnblogs.com/zcxnb/p/18472678