Chapter 5 动态规划

知识

模板

1. 背包问题

(1) 0-1 背包

二维朴素:

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;

int f[N][N];
int v[N], w[N];
int n, m;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; 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]);
        }
    }

    cout << f[n][m] << endl;
    return 0;
}

一维优化: j 按 "从大向小" 的顺序枚举

从 f[i-1][XX] 转移而来, 要用从大到小; 若从 f[i][XX] 转移而来, 那就从小到大 比如这里: f[i - 1][j - v[i]] + w[i]) -> "从大到小"

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;

int f[N];
int v[N], w[N];
int n, m;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) { // j 从大到小
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

    cout << f[m] << endl;
    return 0;
}

(2) 完全背包

二维朴素: 递推找规律

#include<iostream>
using namespace std;

const int N = 1010;

int f[N][N];
int v[N],w[N];

int main()
{
    int n,m;
    cin >> n >> m;
    for (int i = 1 ; i <= n ;i ++) cin >> v[i] >> w[i];

    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] >= 0)
                f[i][j] = max(f[i][j], f[i][j-v[i]] + w[i]);
        }
    }

    cout << f[n][m] <<endl;
    return 0;
}

一维优化: j 按 "从小到大" 的顺序枚举

这里: f[i][j - v[i]] + w[i]) -> "从小到大"

#include<iostream>
using namespace std;

const int N = 1010;

int f[N];
int v[N], w[N];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for (int i=1; i<=n; i++)
        for (int j=v[i]; j<=m; j++) // j 从小到大
            f[j] = max(f[j], f[j-v[i]] + w[i]);

    cout << f[m] <<endl;
    return 0;
}

(3) 分组背包

二维朴素: 递推无规律, 硬着头皮 hard-coding

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i] >> s[i];

    for (int i = 1; i <= n; i ++)
        for (int j = 0; j <= m; j ++)
            for (int k = 0; k <= s[i] && k * v[i] <= j; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);

    cout << f[n][m] << endl;
    return 0;
}

一维优化: 二进制优化 -> 转化成0-1背包 -> "从大到小"枚举

#include<iostream>
using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N]; // 逐一枚举最大是N*logS
int f[M];       // 体积 < M

int main()
{
    cin >> n >> m;
    int cnt = 0; // 分组的组别

    for (int i = 1; i <= n; i ++)// n个 "物品堆"
    {
        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; // s 要减小
            k *= 2; // 组别里的个数增加
        }
        // 剩余的一组
        if (s > 0)
        {
            cnt ++;
            v[cnt] = a * s; 
            w[cnt] = b * s;
        }
    }

    n = cnt ; // 枚举次数 由 个数 变成 组别数

    // 01背包一维优化
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= v[i]; j--) // j 从大到小
            f[j] = max(f[j], f[j-v[i]] + w[i]);

    cout << f[m] << endl;
    return 0;
}

(4) 分组背包

二维朴素: 递推无规律, 硬着头皮 hard-coding

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;

int n,m;
int v[N][N],w[N][N],s[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    for (int i=1; i<=n; i++) {
        cin >> s[i];
        // 第i个物品组 的 第j个物品 的体积和价值
        for (int j=1; j<=s[i]; j++) cin >> v[i][j] >> w[i][j];
    }

    for (int i=1; i<=n; i++) {
        for (int j=0; j<=m; j++) {
            f[i][j] = f[i - 1][j];
            for (int k=0; k<=s[i]; k++) {
                if (j >= v[i][k]) f[i][j] = max(f[i][j],f[i - 1][j - v[i][k]] + w[i][k]);
            }
        }
    }

    cout<<f[n][m]<<endl;
    return 0;
}

一维优化: j 按 "从大到小" 的顺序枚举

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;

int n,m;
int v[N][N],w[N][N],s[N];
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++) {
            cin >> v[i][j] >> w[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= 0; j--) { // j 从大到小
            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;
    return 0;
}

2. 线性DP

(1) 数字三角形

f[i][j]: 从起点走到[i][j]位置时, 累计的价值max

#include <iostream>
#include <cstring>
using namespace std;

const int N = 510, INF = 1e9;

int n;
int a[N][N],f[N][N];

int main () 
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++) 
            cin >> a[i][j];

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= i + 1; j++)
            f[i][j] = -INF;

    f[1][1] = a[1][1];
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= i; j++)
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];

    int ans = -INF;
    for (int i = 1; i <= n; i++) ans = max(ans, f[n][i]);
    cout << ans << endl;

    return 0;
}

(2) 最长上升子序列

给定一个长度为 N 的数列, 求数值严格单调递增的子序列的长度最长是多少

f[i]: 以第 i 个元素为结尾的最长上升子序列的长度

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int a[N], f[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];

    for (int i = 1; i <= n; i ++)
    {
        f[i] = 1; // 只有 a[i] 一个数
        for (int j = 1; j < i; j ++ )
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);

    cout << res <<endl;
    return 0;
}

(3) 最长公共子序列

给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少

#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int N = 1010;

int n, m;
string a, b;
int f[N][N];

int main() 
{
    cin >> n >> m;

    string temp_a, temp_b;
    cin >> temp_a >> temp_b;
    a = " " + temp_a;
    b = " " + temp_b;

    // 注意下标必须从1开始, 不然i-1之类的就error了
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i] == b[j])
                f[i][j] = f[i - 1][j - 1] + 1;
            else
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        }
    }

    cout << f[n][m] <<endl;
    return 0;
}

[!tip] 学习一下如何让 string 不是 0_indexed 而是 1_indexed string temp_a, temp_b; cin >> temp_a >> temp_b; a = " " + temp_a; b = " " + temp_b;

(4) 最短编辑距离

f[i][j]: 第一个字符串的前 i 个字母 变为 第二个字符串的前 j 个字母 所用的最少操作次数

#include <iostream>
#include <string>
using namespace std;
const int N = 1010;

string a, b; //分别存放两个字符串
string tmp_a, tmp_b;
int f[N][N]; //存储结果

int n, m; //两个字符串的长度

int main()
{
    cin >> n;
    cin >> tmp_a;
    a = " " + tmp_a;

    cin >> m;
    cin >> tmp_b;
    b = " " + tmp_b;

    // 边界，a 字符串的前 i 个字符变为 b 字符串的前 0 个字符，需要 i 步(删除)
    for (int i = 0; i <= n; i++) f[i][0] = i;
    // 边界，a 字符串的前 0 个字符变为 b 字符串的前 i 个字符，需要 i 步(插入)
    for (int i = 0; i <= m; i++) f[0][i] = i;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <=m; j++)
        {
            // 情况1 + 情况2
            f[i][j] = min(f[i][j - 1] + 1, f[i - 1][j] + 1);
            // 情况3
            if (a[i] != b[j]) 
                f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
            else 
                f[i][j] = min(f[i][j], f[i - 1][j - 1]);
        }
    }

    // f[n][m] 表示 a 字符传递额前 n 个字符变为 b 字符传递额前 m 个字符需要的最少步骤
    cout << f[n][m] <<endl;
    return 0;
}

3. 区间DP

区间 DP 常用模版:

1. 第一维通常是枚举区间长度
2. 一般 len = 1 时用来初始化，枚举从 len = 2 开始
3. 第二维枚举起点 i (右端点 j 自动获得, j = i + len - 1)

for (int len = 1; len <= n; len++) {         // 1D枚举 区间长度
    for (int i = 1; i + len - 1 <= n; i++) { // 2D枚举 枚举起点
        int j = i + len - 1;                 // 自动出 区间终点

        // 边界初始化
        if (len == 1) {
            dp[i][j] = 初始值
            continue;
        }

        // 枚举分割点，构造状态转移方程
        for (int k = i; k < j; k++) {
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
        }
    }
}

石子合并: 合并 N 堆石子，每次只能合并相邻的两堆石子，求最小代价

#include <iostream>
#include <cstring>
using namespace std;

const int N = 307;

int a[N], s[N];
int f[N][N];

int main() 
{
    int n;
    cin >> n;

    // 利用前缀和, 预处理 a[i~j] 的和
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        s[i] += s[i - 1] + a[i];
    }

    memset(f, 0x3f, sizeof f);

    // 区间 DP 枚举套路: 长度 + 左端点
    for (int len = 1; len <= n; len ++) // 1D枚举 区间长度
    {
        for (int i = 1; i + len - 1 <= n; i ++) // 2D枚举 枚举起点
        {
            int j = i + len - 1; // 自动得到右端点
            if (len == 1) {
                f[i][j] = 0;  // 边界初始化
                continue;
            }

            for (int k = i; k <= j - 1; k ++) { // 分割点k需满足 k <= j - 1
                f[i][j] = min(f[i][j], f[i][k]+f[k + 1][j] + s[j]-s[i-1]);
            }
        }
    }

    cout << f[1][n] << endl;
    return 0;
}

4. 计数类DP

整数划分: 一个正整数n可以表示成若干个正整数之和

本质: 把1,2,3, … n分别看做n个物体的体积，这n个物体均无使用次数限制，问恰好能装满总体积为n的背包的总方案数（完全背包问题变形）

状态: f[i][j] 表示前 i 个整数（1, 2, …, i）恰好拼成 j 的方案数

求方案数：把集合选0个i，1个i，2个i，…全部加起来
    f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2 * i] + ...;
    f[i][j - i] = f[i - 1][j - i] + f[i - 1][j - 2 * i] + ...;

因此 f[i][j]=f[i−1][j]+f[i][j−i]; (这一步类似完全背包的推导）

// f[i][j] = f[i - 1][j] + f[i][j - i]
#include <iostream>

using namespace std;

const int N = 1e3 + 7, mod = 1e9 + 7;

int f[N][N];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i <= n; i ++) {
        f[i][0] = 1; // 容量为0时，前 i 个物品全不选也是一种方案
    }

    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= n; j ++) {
            f[i][j] = f[i - 1][j] % mod; // 特殊 f[0][0] = 1
            if (j >= i) f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;
        }
    }

    cout << f[n][n] << endl;
}

[!tip] 注意 DP初值问题 1. 求最大值时，当都不选时，价值显然是 0 2. 求方案数时，当都不选时，方案数是 1（即前 i 个物品都不选的情况也是一种方案），所以需要初始化为 1

5. 数位统计DP

计数问题: 给定两个整数 a 和 b，求 a 和 b 之间的所有数字中 0∼9 的出现次数

例如，a=1024，b=1032，则 a 和 b 之间共有 9 个数如下：

1024 1025 1026 1027 1028 1029 1030 1031 1032

其中 0 出现 10 次，1 出现 10 次，2 出现 7 次，3 出现 3 次 ......

太难了，要是真考就认栽了

#include <iostream>
#include <vector>

using namespace std;

int base[10];
int f[10][10];
int g[10][10];

void init()
{
    base[0] = 1;
    for(int i = 1 ; i <= 9 ; i++) base[i] = base[i-1]*10;

    //从00……0 - 99……9 的各位数字有多少个，其中i为数字个数（包含前导零）
    for(int i = 0 ; i <= 9 ; i++) f[1][i] = 1;
    for(int i = 2 ; i <= 9 ; i++)
        for(int j = 0 ; j <= 9 ; j++)
            f[i][j] = f[i-1][j]*10 + base[i-1];

    //从1 - 99……9 的各位数字有多少个，其中i为数字个数（不包含前导零）
    for(int i = 1 ; i <= 9 ; i++) g[1][i] = 1;//循环从1开始
    for(int i = 2 ; i <= 9 ; i++) {
        g[i][0] = g[i-1][0] + f[i-1][0]*9;
        for(int j = 1 ; j <= 9 ; j++)
            g[i][j] = g[i-1][j] + f[i-1][j]*9 + base[i-1];
    }
}

vector<int> dp(int n)
{
    vector<int> ans(10,0); //记录答案
    if(n<=0) return ans; //边界条件

    vector<int> nums;
    while(n) nums.push_back(n%10), n/=10;

    vector<int> last(10,0); //记录前缀中各个数字个数

    //统计1 - 99……9(n-1个9)里面各个数字有多少个
    for(int i = 0 ; i <= 9 ; i++) ans[i] = g[nums.size()-1][i];
    //统计大于10……0(n-1个0) 的树里各个数字有多少个
    for(int i = nums.size()-1 ; i >=0 ; i--) {
        //循环变量i可以表示剩下的数字有多少个
        int x = nums[i];
        for(int j = i==nums.size()-1 ; j < x ; j++) { //第一次循环不能有0
            //前缀部分
            for(int k = 0 ; k <= 9 ; k++)
                ans[k] += last[k] * base[i];
            //当前位置部分
            ans[j] += base[i];
            //后缀部分
            for(int k = 0 ; k <= 9 ; k++)
                ans[k] += f[i][k];
        }
        //更新前缀计数器
        last[x] ++;

        //统计叶子节点（这个数本身）
        if(!i) for(int k = 0 ; k <= 9 ; k++) ans[k] += last[k];
    }
    return ans;
}

vector<int> ask(int a, int b)
{
    auto x = dp(b);
    auto y = dp(a-1);
    vector<int> ans;
    for(int i = 0 ; i <= 9 ; i++) ans.push_back(x[i]-y[i]);
    return ans;
}

void print(vector<int> ans)
{
    for(auto x:ans) printf("%d ",x);
    puts("");
}

bool check(int x)
{
    auto t = ask(x,x);
    vector<int> cnt(10,0);
    while(x) cnt[x%10]++,x/=10;
    for(int i = 0 ; i <= 9 ; i++)
        if(cnt[i] != t[i])
            return false;
    return true;
}

int main()
{
    init();

    //这里是一个DEBUG函数
    // for(int i = 1 ; i <= 1000000 ; i*=10) {
    //     if(!check(i))
    //         printf("ERROR:%d\n",i);
    // }

    int a,b;
    while(cin >> a >> b, a||b) {
        if(a>b) swap(a,b);
        auto t = ask(a,b);
        print(t);
    }

    return 0;
}

6. 状态压缩DP

[!tip] 状态压缩DP本质 所谓的状态压缩DP，就是用二进制数保存状态。为什么不直接用数组记录呢？因为用一个二进制数记录方便作位运算。前面做过的八皇后，八数码，也用到了状态压缩。

蒙德里安的梦想: 铺砖块

二进制数 表示 每个是否"出头"

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 12, M = 1 << N;

int n, m;
long long f[N][M];
bool st[M];

int main()
{
    while (cin >> n >> m, n || m)
    {
        for (int i = 0; i < 1 << n; i ++ )
        {
            int cnt = 0;
            st[i] = true;
            for (int j = 0; j < n; j ++ )
                if (i >> j & 1)
                {
                    if (cnt & 1) st[i] = false;
                    cnt = 0;
                }
                else cnt ++ ;
            if (cnt & 1) st[i] = false;
        }

        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for (int i = 1; i <= m; i ++ )
            for (int j = 0; j < 1 << n; j ++ )
                for (int k = 0; k < 1 << n; k ++ )
                    if ((j & k) == 0 && st[j | k])
                        f[i][j] += f[i - 1][k];

        cout << f[m][0] << endl;
    }
    return 0;
}

最短Hamilton路径: 从 0 到 n−1 不重不漏地经过每个点恰好一次 ("一笔画问题")

二进制数 表示 每个node走过与否

#include<iostream>
#include<cstring>

using namespace std;

const int N = 20;
const int M = 1 << 20; // 一共最多有 20个1 种状态

int n;
int w[N][N];
int f[M][N];

int main() 
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> w[i][j];

    // 初始化
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;

    for (int state = 1; state < 1 << n; state++) // 从0到111...11 枚举所有state
    {
        if (state & 1) // state必须要包含起点1
        {
            for (int j = 0; j < n; j++) 
            {
                if (state >> j & 1) // 如果当态前点集包含点j, 那么进行状态转移
                {
                    for (int k = 0; k < n; k++) 
                    {
                        if (state ^ (1 << j) >> k & 1)
                        { 
                            // 如果从当前状态经过点集state中, 去掉点j后, state 仍然包含点k, 那么才能从点k转移到点j
                            // 当然这个 if 也可以不加，因为如果 state 去掉第 j 个点后，state 不包含点 k 了
                            // 那么 f[state ^ 1 << j][k] 必然为正无穷，也就必然不会更新 f[state][j]，所以去掉也可以 AC
                            f[state][j] = min(f[state ^ 1 << j][k] + w[k][j], f[state][j]);
                        }
                    }
                }
            }
        }
    }

    cout << f[(1 << n) - 1][n - 1]; // 最后输出 f[111...11][n-1]
    return 0;
}

7. 树形DP

没有上司的舞会: 快乐值max

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 6010;

int n;
int happy[N]; //每个职工的高兴度
int f[N][2]; //上面有解释哦~
int e[N],ne[N],h[N],idx; //链表，用来模拟建一个树
bool has_father[N]; //判断当前节点是否有父节点

void add(int a,int b) { //把a插入树中
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

void dfs(int u) { //开始求解题目
    f[u][1] = happy[u]; //如果选当前节点u，就可以把f[u,1]先怼上他的高兴度

    for(int i = h[u];~i;i = ne[i]){ //遍历树
        int j = e[i];
        dfs(j); //回溯
        //状态转移部分，上面有详细讲解~
        f[u][0] += max(f[j][1],f[j][0]);
        f[u][1] += f[j][0];
    }
}

int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++) scanf("%d",&happy[i]); //输入每个人的高兴度

    // 初始化 (经典建树)
    memset(h,-1,sizeof h); //把h都赋值为-1

    for (int i = 1;i < n;i ++) {
        int a,b; //对应题目中的L,K,表示b是a的上司
        scanf("%d%d",&a,&b); //输入~
        has_father[a] = true; //说明a他有上司
        add(b,a); //把a加入到b的后面
    }

    int root = 1; //用来找根节点

    while(has_father[root]) root ++; //找根节点

    dfs(root); //从根节点开始搜索

    printf("%d\n",max(f[root][0],f[root][1]));
    return 0;
}

8. 记忆化搜索

滑雪:

#include <iostream>
#include <cstdio>
using namespace std;

const int maxn = 300+10;

int r, c;
int a[maxn][maxn];  // 地形
int dp[maxn][maxn]; // dp的结果

int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, 1, -1, 0};

int dp_search(int x, int y)
{
    // 如果已经搜索过了, 直接返回即可
    if (dp[x][y]) return dp[x][y];

    // 该点本身就算"区域", 故边界起点是1
    dp[x][y] = 1;

    for (int i=0; i<4; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];

        if (xx>=1 && xx<=r && yy>=1 && yy<=c && a[xx][yy] < a[x][y])
            dp[x][y] = max(dp[x][y], dp_search(xx, yy) + 1); // 递归
    }

    return dp[x][y];
}

void out()
{
    for (int i=1; i<=r; i++)
    {
        for (int j=1; j<=c; j++)
            cout << dp[i][j] << " ";
        cout <<endl;
    }
    puts("");
    for (int i=1; i<=r; i++)
    {
        for (int j=1; j<=c; j++)
            cout << dp_search(i, j) << " ";
        cout <<endl;
    }
}

int main()
{
    cin >> r >> c;
    for (int i=1; i<=r; i++)
        for (int j=1; j<=c; j++)
            cin >> a[i][j];

    int max_len = -1;
    for (int i=1; i<=r; i++)
        for (int j=1; j<=c; j++)
            max_len = max(max_len, dp_search(i,j));
    cout << max_len <<endl;

    // out();

    return 0;
}