動態(tài)規(guī)劃 DP：狀態(tài)和轉(zhuǎn)移。
經(jīng)典例題：最長上升子序列 LIS
狀態(tài)：f [ i ] 表示以 i 結(jié)尾的上升子序列中的最長長度衙猪。
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int a[55],f[55];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++){
f[i]=1;
for(int j=1;j<=i-1;j++){
if(a[j]<a[i])
f[i]=max(f[i],f[j]+1);
}
}
cout<<f[n]<<endl;
/*for(int i=1;i<=n;i++)
cout<<f[i]<<" ";*/
return 0;
}
大佬說：還可以用二分和線段樹進(jìn)行優(yōu)化（還沒學(xué)到馍乙，后面再補(bǔ)吧）
補(bǔ)充思考：楊輝三角：c [ n ] [ m ] = c [ n - 1 ] [ m ] + c [ n - 1 ] [ m - 1 ] ;
01背包
1、題目：
給 n 個物品垫释，每個物品有體積 vi 以及價(jià)值 wi丝格，取 n 個物品的一個子集，使體積和不超過 m棵譬，并且價(jià)值和盡量
2显蝌、狀態(tài)：
f [ i ] [ j ] 考慮前 i 個物品，占用體積為 j订咸，能得到的最大價(jià)值
3曼尊、轉(zhuǎn)移：
f [ i ] [ j ] = max ( f [ i - 1 ] [ j ] , f [ i - 1 ] [ j - v [ i ] ] + w [ i ] ) ;
考慮第 i 個物品取還是不取，仍嗳隆：f [ i - 1 ] [ j - v [ i ] ] + w [ i ] 不嚷嫫病：f [ i - 1 ] [ j ]
4、空間優(yōu)化：
(1)滾動數(shù)組
########## 0 // i - 1
++++++*+++ 1 // i
數(shù)組 f [ i ] [ j ] 的取值只與上一行有關(guān)父叙，開數(shù)組 f [ 2 ] [ maxn ]
用 f [ i % 2 ] [ i ] 代表當(dāng)前行 f [ ( i - 1 ) % 2 ] [ j ]代表上一行
(2)更近一步：
從后向前更新神郊，j 以后的是當(dāng)前行，j 以前的是上一行趾唱。
<><><><>0
######## ++
<><><><>1
for (int i=1:i<=n;i++)
for (int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
完全背包
1涌乳、題目：
與 01背包 不同，每個物品可以不限制次數(shù)取
稍微修改轉(zhuǎn)移方程即可：
for(int i=1;i<=n;i++)
for(int j=v[i];j<=m;j++)
f[j]=max(f[j],f[j-v[i]]+w[i]);
2甜癞、為什么這個算法就可行呢爷怀？
大佬說：首先想想為什么 01背包 中要按照 v 遞減的次序來循環(huán)。讓 v 遞減是為了保證第 i 次循環(huán)中的狀態(tài) F [ i , v ] 带欢，是由狀態(tài) F [ i - 1 , v - Ci ] 遞推而來。換句話說烤惊，這正是為了保證每件物品只選一次乔煞，保證在考慮 “選入第i件物品” 這件策略時(shí)依據(jù)的是一個絕無已經(jīng)選入第 i 件物品的子結(jié)果 F [ i - 1 , v - Ci ]。而現(xiàn)在完全背包的特點(diǎn)恰是每種物品可選無限件柒室，所以在考慮 “加選一件第 i 種物品” 這種策略時(shí)渡贾，卻正需要一個可能已選入第 i 種物品的子結(jié)果 F [ i , v - Ci ] ，所以就可以并且必須采用 v 遞增的順序循環(huán)雄右。這就是這個簡單的程序?yàn)楹纬闪⒌牡览怼?/p>
多重背包
1空骚、題目：
有 N 種物品和一個容量為 V 的背包纺讲。第 i 種物品最多有 Mi 件可用，
每件耗費(fèi)的空間是Ci囤屹，價(jià)值是Wi熬甚。求解將哪些物品裝入背包
可使這些物品的耗費(fèi)的空間總和不超過背包容量，且價(jià)值總和最大肋坚。
2乡括、基本算法：
因?yàn)閷τ诘?i 種物品有 Mi + 1 種策略：取 0 件，取 1 件…取 Mi 件智厌。令 F[i, v]
表示前 i 種物品恰放入一個容量為 v 的背包的最大價(jià)值诲泌，則有狀態(tài)轉(zhuǎn)移方程：
F [ i , v ] = max{ F [ i - 1 , v - k ? Ci ] + k ? Wi | 0 ≤ k ≤ Mi }
3、利用二進(jìn)制轉(zhuǎn)化為 01背包問題
方法：將第 i 種物品分成若干件 01 背包中的物品铣鹏，其中每件物品有一個系數(shù)敷扫。這件物品的費(fèi)用和價(jià)值均是原來的費(fèi)用和價(jià)值乘以這個系數(shù)。令這些系數(shù)分別為1, 2, 2 ^ 2. . . 2 ^ ( k - 1 ), Mi - 2 ^ ( k + 1 )诚卸，且 k 是滿足 Mi - 2 ^ ( k + 1 ) > 0 的最大整數(shù)葵第。
例如:如果 Mi 為 13，則相應(yīng)的 k = 3惨险，這種最多取 13 件的物品應(yīng)被分成系數(shù)分別為 1, 2, 4, 6 的四件物品羹幸。這樣就將第 i 種物品分成了 O ( log Mi ) 種物品
#include<iostream>
using namespace std;
const int N=11010,M=2010;
int n,m;
int V[N],W[N];
int f[M];
int main()
{
cin>>n>>m;
int cnt=1;
for(int i=1;i<=n;i++) //拆分打包
{
int v,w,s;
cin>>v>>w>>s;
int k=1;
while(k<=s)
{
V[cnt]=v*k;
W[cnt]=w*k;
s-=k;
k*=2;
cnt++;
}
if(s>0)
{
V[cnt]=s*v;
W[cnt]=s*w;
cnt++;
}
}
for(int i=1;i<=cnt;i++)
for(int j=m;j>=V[i];j--)
f[j]=max(f[j],f[j-V[i]]+W[i]);
cout<<f[m]<<endl;
return 0;
}
