前言
马上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])
\]
区别：
方式一是通过上一维来推导这一维，方式二是通过这一维推导下一维
