+ 感觉要写好久.. 但确实考的很多状态表示：f[i, j] 所有从起点走到(i, j)的路径中数字和最大值
f[i, j] = max(f[i - 1, j - 1] + a[i, j], f[i - 1, j - 1])
状态表示：f[i], 以i结尾的序列长度
记录方案：额外开一个数组 保存转移的过程
for(int i = 1; i <= n; i++)
{
f[i] = 1; // 默认序列长度只有自己
g[i] = 0;
for(int j = 1; j < i; j++) {
if(a[j] < a[i]) { // 单调
if(f[i] < f[j] + 1) {
f[i] = f[j] + 1;
g[i] = j; // 保留转移过程
}
}
}
}
// 找到最优解
int k = 1;
for(int i = 1; i <= n; i ++)
if(f[k] < f[i]) k = i;
for(int i = 0, len = f[k]; i < len; i++){
cout << a[k] << endl;
k = g[k];
}o(nlogn)版本：
最小值一定是单调递增的，所以对于最长子序列而言，只用在每种长度有一个结尾更小的;
因此找到最大的 小于a_i的书 直接更新最小值 a_i+1
int cnt = 0;
f[cnt++] = w[0];
for(int i = 1; i < n; i++) {
if(w[i] > f[cnt - 1]) f[cnt++] = w[i];
else {
int l = 0, r = cnt - 1;
while(l < r) {
int mid = l + r >> 1;
if(f[mid] >= w[i]) r = mid;
else l = mid + 1;
}
f[r] = w[i];
}
cout << cnt << endl;
}状态表示：f[i, j]表示第一个字符串从0-i, 第二个字符串从0-j，无需以当前元素结尾；
f[i, j ] = max(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1] + 1);
word1 = " " + word1, word2 = " " + word2;
for(int i = 1; i <= n; i++)
f[i][0] = i;
for(int i = 1; i <= m; i++)
f[0][i] = i;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
if(word1[i] == word2[j])
f[i][j] = min(f[i][j], f[i - 1][j - 1]);
else
f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
}
return f[n][m];s = ' ' + s, p = ' ' + p;
f[0][0] = true;
for(int i = 0; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(j + 1 <= m && p[j + 1] == '*') continue;
if(i && p[j] != '*')
f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
else if (p[j] == '*')
f[i][j] = f[i][j - 2] || (i && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.'));
}
}状态表示：f[i, j] 用j个鸡蛋，尝试i次可以得到的最高高度
f[i, j] = f[i - 1, j] + 1 + f[i - 1, j - 1]
状态表示：f[i, j]表示只能从前i个物品里选，总体积 <= j的方案
优化：只用到j - vi 一维数组 从右向左更新
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]);
}
cout << f[m] << endl;除了遍历顺序是从左到右，剩下和0-1背包问题完全一致
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]);
}
cout << f[m] << endl;优化方式：二进制打包优化；
while(T--) {
int a, b, s;
cin >> a >> b >> s;
int k = 1;
while(k <= s) {
cnt ++;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
}
n = cnt;
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]);
}
cout << f[m] << endl;问题：分组，每组只能选一个 因此多了一个遍历组的过程 -> 组内0/1背包
//s[i] 每个组有多少item，v[i][j], w[i][j],
for(int i = 1; i <= n; i++)
for(int j = m; j >= 0; j++){
// 多了一步遍历组内item的过程
for(int k = 0; k <= s[i]; k++)
{
if(j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}
}
cout << f[m] << endl;f[i, j] = max(f[i - 1, j], f[i - 1, j - v[i]] + w[i]);
最后输出f[n, m]
其实是判断每个物品是否备选，倒退出来再这个状态转移方程中，选择是的第一项还是第二项
具体区别：
- 不能用状态压缩的方式 -> 两维状态循环无所谓
- 判断f[n][m]倒退，判断是否从上一状态转移过来
0-1背包问题求方案： （字典序最小-> 贪心的选（可选可不选，因为字典序最小，就要选）
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++) {
f[i][j] = f[i - 1][j];
if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
// 输出方案
int j = m;
for(int i = n; i >= 1; i--)
{
if(j >= v[i] && f[i][v] == f[i - 1][j - v[i]] + w[i]){
cout << i << ' ';
j -= v[i];
}
}最优解的方案数 -> 有点像路径条数
f[i, j]
新开一个g[i, j] f[i, j] 取最大值的方案数
分三种情况：
- f[i - 1, j] 大 g[i - 1][j]
- f[i - 1, j - v[i]] + w[i] 大, g[i - 1, j - v[i]]
- 相等：两个想加
-> 可以用一维来写
for(int i = 0; i <= m; i ++) cnt[i] = 1;
for(int i = 1; i <= n; i ++) {
int v, w;
scanf("%d%d", &v, &w);
for(int j = m; j >= v; j --) {
int value = f[j - v] + w;
if(value > f[j]) {
f[j] = value;
cnt[j] = cnt[j - v];
} else if(value == f[j]) {
cnt[j] = (cnt[j] + cnt[j - v]) % mod;
}
}
}