动态规划

• 动态规划问题

  • 1. 数字三角形模型

  • 2. 最长上升子序列模型

  • 3. 背包问题合集

  • 4. 状态机模型

  • 5. 状态压缩DP

  • 6. 区间DP

  • 7. 树形DP

  • 8. 数位DP

  • 9. 单调队列优化的DP问题

+ 感觉要写好久.. 但确实考的很多

动态规划问题

1. 数字三角形模型

状态表示：f[i, j] 所有从起点走到(i, j)的路径中数字和最大值

f[i, j] = max(f[i - 1, j - 1] + a[i, j], f[i - 1, j - 1])

2. 序列问题

2.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;
}

2.2 最长公共子序列

状态表示：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);

2.3 编辑距离

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];

2.4 正则表达式匹配

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] == '.'));
    }
}

2.5 高楼扔鸡蛋

状态表示：f[i, j] 用j个鸡蛋，尝试i次可以得到的最高高度

f[i, j] = f[i - 1, j] + 1 + f[i - 1, j - 1]

3. 背包问题合集

3.1 0-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;

3.2 完全背包问题

除了遍历顺序是从左到右，剩下和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;

3.3 多重背包问题

优化方式：二进制打包优化；

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;

3.4 分组背包问题

问题：分组，每组只能选一个 因此多了一个遍历组的过程 -> 组内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;

3.5 背包问题求具体方案

f[i, j] = max(f[i - 1, j], f[i - 1, j - v[i]] + w[i]);

最后输出f[n, m]

其实是判断每个物品是否备选，倒退出来再这个状态转移方程中，选择是的第一项还是第二项

具体区别：

1. 不能用状态压缩的方式 -> 两维状态循环无所谓

2. 判断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];
    }
}

3.6 背包问题求方案数

最优解的方案数 -> 有点像路径条数

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;
            }
        }
    }

4. 状态机模型

5. 状态压缩DP

6. 区间DP

7. 树形DP

8. 数位DP

9. 单调队列优化的DP问题