動態(tài)規(guī)劃
動態(tài)規(guī)劃算法通趁剑基于一個遞推公式及一個或多個初始狀態(tài)。 當(dāng)前子問題的解將由上一次子問題的解推出抚太。使用動態(tài)規(guī)劃來解題只需要多項式時間復(fù)雜度， 因此它比回溯法昔案、暴力法等要快許多尿贫。
狀態(tài)和狀態(tài)轉(zhuǎn)移方程
例子：01背包問題
有 n 個價值和重量分別為 v[i] 和 w[i] 的物品和一個容量為 m 的背包，要從中選出總重量不超過 m 的物品放入背包踏揣，問所有方案中價值總和的最大值庆亡。
輸入
n=4
(w,v)={(2,3),(1,2),(3,4),(2,2)}
w=5
輸出
7(選擇0,1,3號物品)
狀態(tài)： dp[i][j] 表示考慮前 i 個物品，背包容量為 j 時的最大價值
初始： dp[n][j] = 0
狀態(tài)轉(zhuǎn)移方程：
狀態(tài)轉(zhuǎn)移方程
圖解
int dp[N][N];
void solve(){
for (int i=n-1;i>=0;i--){
for(int j=0;j<=w;j++){
if(j<w[i])
dp[i][j]=dp[i+1][j];
else
dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);
}
}
printf("%d\n",dp[0][w]);
}
