动态规划

BraumAce2024年7月1日约 5488 字大约 18 分钟

动态规划

1. 背包问题

背包问题常用枚举方法

第一维枚举物品
第二维枚举体积
第三维枚举决策

1.1 01 背包

有 $n$ 件物品，背包容量为 $m$ ，每件物品只能使用一次。

求所选物品的总体积不超过背包容量的条件下，最大的总价值。

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

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

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 = 0; j <= m; j++){
            f[i][j] = f[i - 1][j]; //左半边的子集
            if (v[i] <= j) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    }

    cout << f[n][m] << endl;
    */

    //一维
    //f[i] 表示总体积是i的情况下，最大价值是多少
    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;

    return 0;
}

1.2 完全背包

有 $n$ 件物品，背包容量为 $m$ ，每件物品只能使用无限次。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1100;

int n, m;
int v[N], w[N];
int f[N];  //表示总体积是i的情况下，最大价值是多少

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

    cout << f[n][m] << endl;
    */

    //一维
    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;

    return 0;
}

1.3 多重背包

有 $n$ 件物品，背包容量为 $m$ ，每件物品有有限个。

数据范围 $\leq 100$ 的写法：

#include <iostream>
#include <cstring>
#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 = 1; 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;
    
    /* 一维优化写法
    for (int i = 1; i <= n; i++){
        for (int j = m; j >= v[i]; j--){
            for (int k = 0; k <= s[i] && k * v[i] <= j; k++)
            f[j] = max(f[j], f[j - k * v[i]] + w[i] * k);
        }
    }
    cout << f[m] << endl;
    */

    return 0;
}

数据范围较大时，需要用多重背包的二进制优化方法：

第一种写法：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 12010, M = 2010;

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

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

    int cnt = 0;
    for (int i = 1; i <= n; i++){
        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;
        }
        if (s){
            cnt++;
            v[cnt] += a * s;
            w[cnt] += b * s;
        }
    }

    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;

    return 0;
}

第二种写法：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2010;

int n, m;
int f[N];

struct Good
{
    int v, w;
};

int main()
{
    vector<Good> goods;

    cin >> n >> m;
    for (int i = 0; i < n; i++){
        int v, w, s;
        cin >> v >> w >> s;
        for (int k = 1; k <= s; k *= 2){
            s -= k;
            goods.push_back({v * k, w * k});
        }
        if (s > 0) goods.push_back({v * s, w * s});
    }

    for (auto good : goods){
        for (int j = m; j >= good.v; j--){
            f[j] = max(f[j], f[j - good.v] + good.w);
        }
    }

    cout << f[m] << endl;

    return 0;
}

1.4 分组背包

有 $n$ 组物品和一个容量是 $m$ 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

（一）第一种写法：

#include <iostream>
#include <cstring>
#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 = 0; 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--){
            for (int k = 0; k < s[i]; k++){
                if (v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
            }
        }
    }

    cout << f[m] << endl;

    return 0;
}

（二）第二种写法：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;

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

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

    for (int i = 0; i < n; i++)
    {
        int s;
        cin >> s;

        for (int j = 0; j < s; j++) cin >> v[j] >> w[j];

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

    cout << f[m] << endl;

    return 0;
}

2. 线性DP

2.1 数字三角形

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

线性DP写法：

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

const int N = 510, INF = 1e9;

int n;
int a[N][N];
int 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;


    /*从下往上遍历
    for (int i = n; i >= 1; i--)
        for (int j = n; j >= 1; j--)
            f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + a[i][j];

    cout << f[1][1] << endl;
    */

    return 0;
}

2.2 最长上升子序列

求一个序列中严格递增的子序列的最大长度。

（一）朴素DP写法：

状态转移方程：if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);

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

int n;
int a[N];
int 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[1]一个数
        for (int j = 1; j <= i; j++)
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }

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

    cout << ans << endl;

    return 0;
}

（二）二分写法：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;

int n;
int q[N];
int a[N];

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

    int len = 0;
    q[0] = -2e9;
    for (int i = 0; i < n; i++)
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }

    cout << len << endl;

    return 0;
}

（三）单调队列写法：

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100010;

int n;

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

    vector<int> stk; //模拟堆栈
    stk.push_back(arr[0]);

    for (int i = 1; i < n; i++) //单调队列思维
    {
        if (arr[i] > stk.back()) //如果该元素大于栈顶元素，则将该元素入栈
            stk.push_back(arr[i]);
        else //否则，替换掉第一个大于或等于这个数字的那个数
            *lower_bound(stk.begin(), stk.end(), arr[i]) = arr[i];
    }

    cout << stk.size() << endl;

    return 0;
}

2.3 最长公共子序列（不连续）

给定两个长度分别为 $n$ 和 $m$ 的字符串 A 和 B，

求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

状态转移方程：

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

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

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

int main()
{
    cin >> n >> m >> a + 1 >> b + 1;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (a[i] == b[j])
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }

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

    return 0;
}

2.4 最长公共上升子序列

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。

小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。

小沐沐说，对于两个数列 $A$ 和 $B$ ，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。

奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。

不过，只要告诉奶牛它的长度就可以了。

数列 $A$ 和 $B$ 的长度均不超过 $3000$ 。

输入格式

第一行包含一个整数 $N$ ，表示数列 $A, B$ 的长度。
第二行包含 $N$ 个整数，表示数列 $A$ 。
第三行包含 $N$ 个整数，表示数列 $B$ 。

输出格式

输出一个整数，表示最长公共上升子序列的长度。

数据范围

$1≤N≤3000$ , 序列中的数字均不超过 $2^{31}−1$ 。

输入样例：

4
2 2 1 3
2 1 2 3

输出样例：

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3010;

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

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    
    for (int i = 1; i <= n; i++){
        int mx = 1;
        for (int j = 1; j <= n; j++){
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j]) f[i][j] = max(f[i][j], mx);
            if (a[i] > b[j]) mx = max(mx, f[i - 1][j] + 1);
        }
    }
    
    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
    
    cout << res << endl;
    
    return 0;
}

2.5 编辑距离

给定 $n$ 个长度不超过 $10$ 的字符串以及 $m$ 次询问，每次询问给出一个字符串和一个操作次数上限。

对于每次询问，请你求出给定的 $n$ 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。

每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

输入格式

第一行包含两个整数 $n$ 和 $m$ 。
接下来 $n$ 行，每行包含一个字符串，表示给定的字符串。
再接下来 $m$ 行，每行包含一个字符串和一个整数，表示一次询问。
字符串中只包含小写字母，且长度均不超过 $10$ 。

输出格式

输出共 $m$ 行，每行输出一个整数作为结果，表示一次询问中满足条件的字符串个数。

模板代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15, M = 1010;

int n, m;
int f[N][N];
char str[M][N];

int edit_distance(char a[], char b[])
{
    int la = strlen(a + 1), lb = strlen(b + 1);
    
    for (int i = 0; i <= la; i++) f[i][0] = i;
    for (int j = 0; j <= lb; j++) f[0][j] = j;
    
    for (int i = 1; i <= la; i++)
        for (int j = 1; j <= lb; j++)
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            if (a[i] == b[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[la][lb];
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> str[i] + 1; //下标从1开始存
    
    while (m--){
        char s[N];
        int limit;
        cin >> s + 1 >> limit;
        
        int res = 0;
        for (int i = 0; i < n; i++)
            if (edit_distance(str[i], s) <= limit)
                res++;
                
        cout << res << endl;
    }
    
    return 0;
}

2.6 最短编辑距离

给定两个字符串 $A$ 和 $B$ ，现在要将 $A$ 经过若干操作变为 $B$ ，可进行的操作有：

删除 – 将字符串 $A$ 中的某个字符删除。
插入 – 在字符串 $A$ 的某个位置插入某个字符。
替换 – 将字符串 $A$ 中的某个字符替换为另一个字符。

现在请你求出，将 $A$ 变为 $B$ 至少需要进行多少次操作。

状态转移方程：

f[i][j] = min(f[i-1][j] + 1, f[i][j-1] + 1);
if (a[i] == b[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); //状态转移方程

代码：

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

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N]; //所有将a[i]变成b[j]的操作方式

int main()
{
    cin >> n >> a + 1;
    cin >> m >> b + 1;
    
    for (int i = 0; i <= n; i++) f[i][0] = i;
    for (int j = 0; j <= m; j++) f[0][j] = j;
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            if (a[i] == b[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);
        }
    
    cout << f[n][m] << endl;
    
    return 0;
}

3. 区间DP

区间 DP 常用模版

所有的区间 dp 问题枚举时，

第一维通常是枚举区间长度，并且一般 len = 1 时用来初始化，枚举从 len = 2 开始；

第二维枚举起点 $i$ （右端点 $j$ 自动获得，j = i + len - 1）

模板代码如下：

for (int len = 1; len <= n; len++) {         // 区间长度
    for (int i = 1; i + len - 1 <= n; i++) { // 枚举起点
        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]);
        }
    }
}

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 310;

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

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    
    //区间DP枚举套路：长度+左端点 
    for (int len = 2; len <= n; len++)  //先枚举长度
    {
        for (int i = 1; i + len - 1 <= n; i++)  //再枚举左端点，且保证右端点不会超范围
        {
            int j = i + len - 1; //自动得到右端点
            
            f[i][j] = 1e9;  //初始化大于1的区间为最大，长度为1的区间为0
            for (int k = i; k <= j - 1; k++)  
                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 可以表示成若干个正整数之和，我们将这样的一种表示称为正整数 n 的一种划分。现在给定一个正整数 n，请你求出 n共有多少种不同的划分方法。

表示前 $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;
}

一维优化：

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

5. 数位统计类DP

给定两个整数 $a$ 和 $b$ ，求 $a$ 和 $b$ 之间的所有数字中 0 ~ 9 的出现次数。

#include <bits/stdc++.h>
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();

    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

6.1 蒙德里安的梦想

$n×m$ 的棋盘可以摆放不同的 $1×2$ 小方格的种类数。

状态表示： $f[i][j]$ 表示当前摆到第 $i$ 列的状态是 $j$ 的所有方案。

(其中 $j$ 是一个二进制数，用来表示哪一行的小方块是横着放的，其位数和棋盘的行数一致。)

去除无效状态的优化写法：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << N;

int n, m;
LL f[N][M];
vector<int> state[M];
bool st[M];

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

        for (int i = 0; i < 1 << n; i ++ )
        {
            state[i].clear();
            for (int j = 0; j < 1 << n; j ++ )
                if ((i & j) == 0 && st[i | j])
                    state[i].push_back(j);
        }

        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 (auto k : state[j])
                    f[i][j] += f[i - 1][k];

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

    return 0;
}

6.2 最短Hamilton路径

给定一张 $n$ 个点的带权无向图，点从 $0$ ~ $n-1$ 标号，求起点 $0$ 到终点 $n-1$ 的最短Hamilton路径。

Hamilton 路径的定义是从 $0$ 到 $n-1$ 不重不漏地经过每个点恰好一次。

$f[i][j]$ 表示从 $0$ 走到 $j$ ，走过的所有点的情况是 $i$ 的所有路径。

状态转移方程：f[i][j] = min(f[i][j], f[i-(1<<j)][k] + w[k][j]);

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 20, M = 1 << N;

int n;
int f[M][N], w[N][N];//w表示的是无权图

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;   // 因为零是起点,所以f[1][0]=0;

    for (int i = 0; i < 1 << n; i++)   // i表示所有的情况
    	for (int j = 0; j < n; j++)  // j表示走到哪一个点
      		if (i >> j & 1)
       			for (int k = 0; k < n; k++)  // k表示走到j这个点之前,以k为终点的最短距离
        			if (i >> k & 1)  // 更新最短距离
         				f[i][j] = min(f[i][j], f[i - (1<<j)][k] + w[k][j]);

    // 表示所有点都走过了,且终点是n-1的最短距离
    cout << f[(1<<n) - 1][n - 1] << endl;
    
    return 0;
}

7. 树形DP

7.1 没有上司的舞会

选了某个节点就不能选父节点和子节点。求最大权值和。

每个人只有两种状态，则设 $dp[0][i]$ 为第 $i$ 个人不来，他的下属所能获得的最大快乐值；

$dp[1][i]$ 为第 $i$ 个人来，他的下属所能获得的最大快乐值。

状态转移方程：

$dp[0][i] = \sum_{u=sons} max(dp[1][u], dp[0][u])$ 当前节点不选，那么子节点随意

$dp[1][i] = \sum_{u=sons} dp[0][u] + happy[i]$ 当前节点选，子节点不能选

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

int n;
int dp[2][6010];
int f[2][6010];  // f[0]为父亲，f[1]为高兴值
int ind[6010];   // 入度
int vis[6010];   // 访问标记
int root;        // 树的根

void dfs(int u)  // 递归从后往前更新
{
    if (!u) return;
    vis[u] = 1;  // 已访问
    root = u;    // 最后一个访问到的一定是根，所以一直更新根就行了
    dp[0][f[0][u]] += max(dp[1][u] + f[1][u], dp[0][u]);  // 给父亲更新
    dp[1][f[0][u]] += dp[0][u];
    ind[f[0][u]]--;   // 更新完一个子节点
    if(!ind[f[0][u]]) 
        dfs(f[0][u]); // 在所有子节点更新后再更新（入度为0）
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%d", &f[1][i]);
    
    int a,b;
    for (int i = 1; i < n; i++){
        scanf("%d%d", &a, &b);
        f[0][a] = b;  // 保存节点信息
        ind[b]++;
    }
    
    for (int i = 1; i <= n; i++)
        if(!vis[i] && !ind[i])  // 没有被访问过，没有入度，说明是叶子节点
            dfs(i);
    
    // 取根节点两种方案的最大值
    printf("%d\n", max(dp[0][root], dp[1][root] + f[1][root]));
    
    return 0;
}