经典0-1背包问题
“阶段”是在前i件物品中，选取若干件放入背包中。此时状态为前i件物品中选取若干件放入所剩空间为j的背包中获得的最大价值。
“决策”：第i件物品放或不放，此时动态转移方程为：
(1)如果第i件物品不放入背包.dp[i][j] = dp[i-1][j]即状态转移为前i-1件物品放入所剩空间为j的背包中获得的最大价值。
(2)如果第i件物品放入背包.dp[i][j]=dp[i-1][j-vi]+wi（体积为v，价值为w），即状态转移为前i-1件物品放入所剩空间为j-vi的背包中。此时最大价值为dp[i-1][j-vi]+wi。
案例1：草药总价值最大
输入第一行有2个整数T(1<=T<=1000)和M(1<=M<=100)用一空格隔开。T代表总共能够用来采药的时间。M代表山洞中草药的数目，接下来M行每行包括两个在1到100之间的整数，分别代表摘某株草药的时间和这株草药的价值。
输入：
70 3
71 100
69 1
1 2
输出：3
求解思路：
dp[i][j]：前i株草药在最大采药时间j下的最大价值
for i = 0 : M-1
for j = 0 ：T
if (j >= t[i])
dp[i][j] = max(dp[i-1][j], dp[i-1][j-t[i]]+v[i])
返回dp[M-1][T]
C++代码：
#include<iostream>
#include<cmath>
using namespace std;
int dp[105][105]; //dp[i][j]表示前i+1件草药在最大采药时间j下的最大价值
int p[105];
int t[105];
void DpFindMaxValue(int T, int M) {
for (int i = 0; i < M; i++) {
for (int j = 0; j <= T; j++) {
if (j >= t[i]) {
dp[i][j] = fmax(dp[i - 1][j], dp[i - 1][j - t[i]] + p[i]);
}
}
}
}
int main() {
int T, M;
cin >> T >> M;
for (int i = 0; i < M; i++)
cin >> t[i] >> p[i];
DpFindMaxValue(T, M);
cout << dp[M - 1][T] << endl;
return 0;
}
案例2：最长递增子序列
d[1...9] = 2 1 5 3 6 4 8 9 7
定义一个序列B，然后令i=1 to 9逐个考察这个序列。
首先，把d[1]有序放入B中，令B[1]=2，表示只有1个数字2时，长度为1的LIS的最小末尾为2。len=1.
然后，把d[2]有序放入B中，令B[1]=1表示长度为1的LIS的最小末尾为1，d[1]=2已经没用了。len=1.
接着，d[3]=5，d[3]>B[1]。所以令B[1+1]=B[2]=d[3]=5，表示长度为2的LIS最小末尾是5，B[1...2]=1,5，len=2.
d[4]=3，正好夹在1-5之间，放在1的位置不合适(1<3)，所以长度为2的LIS的最小末尾为3.于是把5淘汰掉，这时B[1...2]=1,3，len=2.
d[5]=6，在3后面B[3]=6，B[1...3]=1,3,6，len=3.
d[6]=4，在3,6之间，把6替换，B[3]=4。B[1...3]=1,3,4，len=3.
d[7]=8，B[4]=8，len=4.
d[8]=9，B[5]=9，len=5.
d[9]=7，在B[3]=4和B[4]=8之间，若B[4]=7，len=4，所以还是保留B[1...5]=1,3,4,8,9，len=5.
求解思路：
状态为当前位置i就能返回值，dp[i]表示以arr[i]结尾的最长递增子序列长度。动态转移方程为：
dp[i]=max{dp[i], dp[j]+1} ,for all j 满足 0<=j<i && arr[i] > arr[j].
C++代码：
for (int i = 0; i < A.length; i++) {
dp[i] = 1; //初始化
for (int j = i - 1; j >= 0; j--) {
if (A[j] < A[i]) {
dp[i] = max{ dp[i], dp[j] + 1 };
}
}
}
案例3：乘积最大
程序输入：
第一行共N，K(6<=N<=40,1<=K<=6)，其中N为数字串位数，K为乘号数目。
第二行长度为N的数字串。
求解思路：
(1)创建二维数组f[][]，用f[i][j]表示前i位数包括j个乘号所能达到的最大乘积。
(2)将i从2到n枚举，表示分割为前i位数字。
(3)对每一次分割再将a从1到min(i-1,k)枚举，表示前i位中含有a个乘号。
(4)将b从a到i-1进行一次枚举，表示前i位中含有a个乘号，且最后一个乘号的位置在b处。
那么当最后一个乘号在b处时最大值为前b位中含有a-1个乘号的最大值乘上b处之后的数字。
(5)因此得出状态转移方程为：
f[i][a]=max(f[i][a], f[b][a-1]*cut(b+1,i))，cut(b+1,i)表示b+1到i位数值。
C++代码：
#include<iostream>
#include<string>
using namespace std;
long long f[45][60];
string in;
int n, k; //n位数,k个乘号
long long g[45];
long long cut(int l, int r) {
long long end = 0;
for (int i = l; i <= r; i++)
end = 10 * end + g[i];
return end;
}
int main() {
cin >> n >> k >> in;
for (int i = 1; i <= n; i++)
g[i] = in[i - 1] - '0';
for (int i = 1; i <= n; i++)
f[i][0] = cut(1, i); //前i位，0个乘号最大乘积
for (int i = 2; i <= n; i++) { //分割前i位数
for (int a = 1; a <= std::fmin(i - 1, k); a++) { //枚举几个乘号
for (int b = a; b < i; b++) { //在第几位放乘号（最后一个）
f[i][a] = std::fmax(f[i][a], f[b][a - 1] * cut(b + 1, i));
}
}
}
cout << f[n][k] << endl;
return 0;
}
