典型的动态问题比如背包问题和线性DP问题, 我们之前都已经解决过了, 我们来看其他常见的DP问题

区间DP

石子合并

设有 N 堆石子排成一排，其编号为 1,2,3,…,N1,2,3,…,。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

例如有 44 堆石子分别为 1 3 5 2， 我们可以先合并 1、21、2 堆，代价为 44，得到 4 5 2， 又合并 1、21、2 堆，代价为 99，得到 9 2 ，再合并得到 1111，总代价为 4+9+11=244+9+11=24；

如果第二步是先合并 2、32、3 堆，则代价为 77，得到 4 7，最后一次合并代价为 1111，总代价为 4+7+11=224+7+11=22。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

状态表示 :

  • 集合: 这类问题我们状态表示的是一个区间
  • 属性: 表示这个区间代价的最小值

状态转移 :

​ 每个区间分别求得代价的最小值, 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 300 + 10;
int a[N], f[N][N];
int n;

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

    // len表示每个区间最小长度
    for(int len = 2; len <= n; len++)
        
        //  从左到右分别递推每个长度为len的区间
        for(int i = 1; i + len - 1 <= n; i++)
        {
            int l = i, r = i + len - 1;
            f[l][r] = 0x3f3f3f3f;
            
            // 在[l, r]区间上用k划分为两个区间,分别求最小值
            for(int k = l; k < r; k++)
            {
              	// 表示的是以k为分界线的左区间和右区间内的最小值, 最后加上区间总共意思是为了最后一步累加的结果
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + a[r] - a[l - 1]);
            }
        }

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

计数类DP

整数划分

一个正整数 n� 可以表示成若干个正整数之和，形如：n=n1+n2+…+nk ，其中 n1 ≥ n2 ≥ … ≥ nk, k ≥ 1。

我们将这样的一种表示称为正整数 n 的一种划分。

现在给定一个正整数 n，请你求出 n 共有多少种不同的划分方法。

状态压缩DP

蒙德里安的梦想

https://www.acwing.com/problem/content/293/

我们以每一列来看, 用一个二进制数来表示当前的状态, 若横置方块, 则一定会想下一行伸出一块. 只要我们定义了横放的方案, 剩下的就一定是竖放的方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

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

long long  f[N][M];
int n,m;
int 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;
                }
                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(st[k | j] && (k & j) == 0) f[i][j] += f[i - 1][k];
        }
        cout << f[m][0] << endl;
    }
    
    return 0;
}