正向Dp

对于很多问题，例如0-1背包问题，很多人都运用的是那种最普遍的DP方式

代码如下：

for i:=1 to n do

for j:=v downto 0 do

dp[j]:=max(dp[j],dp[j-w[i]]+s[i]) {w表示物品的体积，s表示物品的价值}

但是对于这种DP，对于很多初学者来说都会是一个很难理解的问题，而且对于很多背包的变形问题（例如：分组背包问题）却是一种很浪费时间的方法。

所以，在这时候，我们就要用到正向DP的方法。

方法如下：

dp[i]表示体积为i的情况的最大价值是多少。

初始化dp[i]:=-1{1<=i<=v);

if (dp[i]<>-1) and (dp[i+w[j]]<dp[i]+s[j]) then dp[i+w[i]]:=dp[i]+s[i];

目标：dp[v]；

解释：

对于这种正向dp的方法，我们可以在DP的过程中不断的更新v的值，以此达到节省时间的目的。

变形

对于多重背包问题，我们可以运用一个num数组来节省一冲循环，num数组表示体积为i时，用了第j件物品的最少次数，很好的做到了用空间换时间的效果。

大家可以去试试楼天成的男人八题，用正向DP会节省许多时间与代码长度。