安安 DP只是一种工具
也不是说递回的值存起来 多的是跟递回没关系的DP解法
DP会说到递回基本上都是用费伯纳契数列的入门
但有其他的像是01背包问题 就是一个DP比较泛用的例子
DP的重点在于
1. dp[i]定义
2. 状态推导
费伯纳契的dp[i]定义就是 费伯纳契数列的第i+1个数
1, 1, 2, 3, 5, 8.....
因为费伯纳契数列的数 就是该数前两位相加 所以费伯纳契dp[i]的状态推导就是
dp[0] = 1, dp[1] = 1, 那dp[2] = dp[0]+dp[1] = 2
i>=2 dp[i] = dp[i-1] + dp[i-2]
dp[2] 为 费伯纳契数列的第三个数 dp[3] 为第四个 依此列推
任何dp问题 只要把这两个东西找出来 大概90%就完成了
像是01背包问题 dp[i] 就是 当背包空间为i的时候 背包内物品价值最高为多少
他的状态推导 就是 dp[i] = max(dp[i], dp[i - volume[j]] + value[j]);
这个状态推导有点跳 但意思就是说 背包空间为i 装物品j的价值与不装哪个高
举个例子 假设我们 背包空间为50公升
分别有三个物品 每个物品只能放一次
物品A 20公升 价值为$10
物品B 30公升 价值为$5
物品C 50公升 价值为$20
那要怎么装 背包物品的价格会最高?
回到我们刚刚的状态推导
dp[i] = max(dp[i], dp[i - volume[j]] + value[j]);
这边我有点偷懒 用一维矩阵来算dp
所以需要一个小技巧就是从背包空间大到小 01背包问题因为物品只能被放一次
我们要从dp[50]开始
dp[50] = max(dp[50], dp[50-物品C体积]+物品C价值) = 20
只放物品C价值$20 因为物品C空间需要50 所以低于50我们都不用算了
break;
再来是跟放物品B比
dp[50] = max(dp[50]=20, dp[50-物品B体积]+物品B价值) 还是 只放物品C高
同时得到一个有意义的值 dp[49~30] 都是等于 $5
等等我们会用到
再来是跟放物品A比
dp[50] = max(dp[50]=20, dp[50-物品A体积]+物品A价值) 还是 只放物品C高
有趣的是这边 dp[50] = max(dp[50], dp[50-20]+物品A价值)
dp[30]刚刚我们算过 是$5 就是只放物品B的价值 背包空间还有20 还够放个物品A
那dp[30]+物品A的价值 就是 物品A+B的价值 = $15 还是比只放物品C低
最后我们得到 dp[50]当背包空间为50 物品价值最高为$20
这个简单的例子 你用肉眼看就知道 只塞物品C价值最高 A+B也没C高
但是当今天背包空间超大 物品几千个 你人肉眼看不出来 算个老半天也算不出来
但是用一样的dp[i]定义 一样的状态推导 背包从大到小
写个小程式就能把答案算出来了
TLDR
DP只有两个重点
1. dp[i]定义
2. 状态推导
本巨巨祝福大家都能开开心心 轻轻松松学DP 谢谢大家
※ 引述《Nigger5566 (尼哥56)》之铭言：
: DP, Dynamic Programming 动态规划
: 算法的一个章节
: 大概就是把递回的值存起来不用重复回
: 用嘴巴讲的话满简单的
: 学会了DP可以干嘛
: 能去Google上班吗
: 有没有八卦
: