正向DP是一種程式語言。
基本介紹
- 中文名：正向DP
- 類型：程式語言
正向Dp,變形,
正向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會節省許多時間與代碼長度。
