求助，动态规划！

[wemore]

求哪位大神讲解一下动态规划，或者讲动态规划比较清晰的博客地址。新手实在看不太懂，到现在 01 背包也只是看懂了一点。。云里雾里的

[mrsatangel]

这是在作数模？

[wemore]

@mrsatangel 参加竞赛，在题库里遇到很多动态规划题

[jiezhi]

在高中准备 NOIP 的时候好像做过，现在只记得很难了。

[aljun]

可以去看看背包九讲

然后我推荐你先搞懂搜索，动归要说起来其实是记忆了搜索的一些树，做了些“剪枝”

[kindjeff]

找算法的教学 PPT

[changwei]

楼主，我现在 01 背包问题都是云里雾里的啥都没弄明白，就是判断的时候

for(j=0;j<m+1;j++)
for(i=0;i<n+1;i++)
{
if(j<w[i])
{
c[i][j]=c[i-1][j];
continue;
}else if(c[i-1][j-w[i]]+p[i]>c[i-1][j])
c[i][j]=c[i-1][j-w[i]]+p[i];
else
c[i][j]=c[i-1][j];
}

这里 j<w[i]和 c[i-1][j-w[i]]+p[i]>c[i-1][j]这两个条件我没明白是判断什么的，求告知，谢谢= =

[towser]

背包问题就是记忆型搜索，深搜和广搜先学好，之后去找「背包九讲」来看看。

[xjx0524]

@changwei 首先你要知道（ i, j ）这个状态表示背包容量为 j 时前 i 个物品所能达到的最大价值。
j<w[i]意思是第 i 个物品容量 w[i]大于当前背包容量 j ，所以不选物品 i ，当前最大价值 c[i][j]=c[i-1][j]
c[i-1][j-w[i]]+p[i]>c[i-1][j]，大于号右边部分意义和上面一样，代表不选第 i 个物品能达到的最大价值
左边部分表示选上第 i 个物品的最大价值，所以要看（ i-1, j-w[i]）这个状态（意思是前 i-1 个物品里，背包容量为 j-w[i]时的最大价值），这样把容量为 w[i]的物品 i 放进去刚好达到（ i, j ）这个状态，然后在加上物品 i 的价值 p[i]。
比较大于号左右两边的式子，哪个大就用哪个喽

[pandachow]

背包九讲+1

[SuperFashi]

竟然有人在 V2EX 问算法题，吓到。
先推荐个神犇的博客 hzwer.com

DP 的最最主要的部分就是在于状态转移，我们需要求出如何从上一个状态转移到下一个状态，也就是转移方程。
例如背包问题，有一维和二维两种方式，本质都是一样的，但是二维比较好理解，我来说一下。
假设 n 个物品，这 n 个物品的大小在一个数组 weight[n]里面，背包最大装 m ，数组 dp[i][j]， i 表示输入中的前 i 个物品， j 表示背包此时大小， dp[i][j]表示有 i 个物品且背包大小为 j 时最多能装多少东西（或者大小，都是一样的）。
首先对某个物品来说，背包的大小肯定不能小于物品大小，否则装不进去了，也就是 dp[i][]中 weight[i] >= j 。接下来，我们在可以想出，要是想装这个物体， dp[i][j]就是 dp[i - 1][j - weight[i]] + 1 ，但实际上，有的物品不装反而最后能满足的更多，那么我们还要判断是 dp[i - 1][j]大还是 dp[i - 1][j - weight[i]] + 1 大，表示到底装不装这个物品大。
这时候还没完，我们发现，在 weight[i] < j 的这时候，其实我们也可以不装此时这个物品，因为装不进去，但是可以把以前能装的的物品装进去，也就是直接赋为 dp[i - 1][j]。
然后跑个两层 for 就好了，最后 dp[n][m]就是答案。
好好自己想想为什么，不要看到题解似懂非懂就做， AC 也没什么用。
总之背包和区间还好，到时候状压会让你怀疑人生的。

[GtDzx]

可以去看看 http://hihocoder.com/discuss/question/2822 后半部分的教学篇
PS 题目需要注册登录

[lechain]

理解几个概念。 dP 的条件:问题是否能分解为子问题 子问题的求解是否无后效性 还有 最重要的是理解状态 和 转移。还有多做题就好了

[lsylsy2]

背包九讲+2
虽然我不是看它学的，但是写的真的不错

[changwei]

@xjx0524 啊，听你这么一说好像明白了好多(⊙０⊙)还有有一个疑问就是为什么两个 for 的循环结束条件是 m+1 和 n+1 呢？还有这两层循环结束之后， c[][]数组里面是 c[m][n]存的是最大价值还是 c[m+1][n+1]呢？为什么是这样？谢谢谢解答= =

[xjx0524]

@changwei 那是小于号啊朋友。。。
for(j=0;j<m+1;j++)
j 最大是 m 啊

[binux]

动态规划就是带结果缓存的 f(n) = g(f(n-1))

[newton108]

mit 6.006 6.046j

[yhylord]

@SuperFashi 看黄学长的 blog 真是充满励志……从第一条到最后一条……

[linux40]

算法导论上的动态规划讲得很好。

[wizardforcel]

看成带 cache 的递归调用。

背包的转移方程是二维的，语义理解起来也有点困难，不如先找些一维的来做。