算法基础（16）

1.计数类DP

例题：整数划分（Acwing 900）

一个正整数$n$可以表示成若干个正整数之和，形如：$n=n_1+n_2+…+n_k$，其中$n_1≥n_2≥…≥n_k,k≥1$。我们将这样的一种表示称为正整数$n$的一种划分。现在给定一个正整数$n$，请你求出$n$共有多少种不同的划分方法。由于答案可能很大，输出结果请对$10^9+7$取模。

数据范围：$1\le n \le 1000$

因为题中的划分方案不考虑数字的顺序，因此我们可以把要划分的数$n$看作是一个体积为$n$的背包，有体积有$1,2,3,\dots,n$的物品，可取用的个数是无限个，我们要求的是恰好装满背包的方案数，即抽象成完全背包问题。

• 状态表示f(i,j)：
  • 集合：所有从$1\sim i$中选，总体积恰好为$j$的选法的集合
  • 属性：上述选法的数量
• 状态计算：
  • 集合的划分：f(i,j)可以分为选了0个第i个物品f(i-1,j)，选了1个第i个物品f(i-1,j-i)，选了两个第i个物品f(i-1,j-2*i)，……选了s个第i个物品f(i-1,j-s*i)；
  • 状态转移方程为：f(i,j)=f(i-1,j)+f(i-1,j-i)+f(i-1,j-2*i)...+f(i-1,j-s*i)，时间复杂度为$O(n^2 \log n)$（状态数为$n^2$，状态计算量为$\frac{n}{1}+\frac{n}{2}+\frac{n}{3}+\dots\frac{n}{n}=\log n$。
  • 按照完全背包问题的思路做进一步优化：将f(i,j)的方程与f(i,j-i)的方程作对比，f(i,j-i)=f(i-1,j-i)+f(i-1,j-2*i)+...+f(i-1,j-s*i)，则有：f(i,j)=f(i-1,j)+f(i-1,j-i)；同时可以在空间上优化，用一维数组表示，即f[j]=f[j]+f[j-1]，体积从小到大循环。这样时间复杂度为$O(n^2)$

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

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

int n;
int f[N];

int main()
{
    cin >> n;
    
    f[0] = 1;  //初始化：当没有数时，j=0有一种方案，即i=0；其余f[j]都是0
    
    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;
    
    return 0;
}

另一种解法：

• 状态表示f[i,j]：

  • 集合：所有总和是i，并且恰好表示成j个数的和的选法；
  • 属性：数量，上述选法的数量

• 状态计算：

  • 集合划分：f[i,j]可以分为两大类：方案中最小值是1——若把所有方案中的最小值1去掉，就可以变成总和是i-1，恰好分成j-1个数的方案，即f[i-1,j-1]；方案中最小值大于1——若把方案中每个数都减去1，就可以变成总和是i-j，恰好分成j个数的方案，即f[i-j,j]。
  • 则状态转移方程：f[i,j]=f[i-1,j-1]+f[i-j,j]，最后的答案是ans=f[n,1]+f[n,2]+...+f[n,n]

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

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

int n;
int f[N][N];

int main()
{
    cin >> n;
    
    f[0][0] = 1;  //初始化：当没有数时，j=0有一种方案，即i=0；其余f[j]都是0
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
    
    int res = 0;
    for(int i = 1; i <= n; i ++)  res = (res + f[n][i]) % mod; 
            
    cout << res << endl;
    
    return 0;
}

2.数位统计DP

例题：计数问题（Acwing 338）

给定两个整数$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次等等…

输入格式：输入包含多组测试数据。每组测试数据占一行，包含两个整数 a 和 b。当读入一行为0 0时，表示输入终止，且该行不作处理。

输出格式：每组数据输出一个结果，每个结果占一行。每个结果包含十个用空格隔开的数字，第一个数字表示‘0’出现的次数，第二个数字表示‘1’出现的次数，以此类推。

数据范围：$0<a,b<100000000$

显然暴力做法是不可取的，以下做法中最重要的思路是：分情况讨论。直接求从[a,b]中0~9出现的次数是不好求的，我们可以先求count(n,x)，即$1 \sim n$中x出现的次数，再用求前缀和的思路来求[a,b]中x出现的次数，即count(b,x)-count(a-1,x)。

以count(n,1)为例，设当前数字为abcdefg，思路是分别求出1在每一位上出现的次数，如求1在第4位出现的次数，即有多少形如xxx1yyy的数，满足1 <= xxx1yyy <= abcdedfg，分情况讨论：

1. 前三位，xxx = 000~abc-1时，后三位可以取到yyy=000~999，一共有abc * 1000次数；

2. 前三位，xxx=abc：

   (2.1) d < 1，abc1yyy > abc0defg，共0次数；

   (2.2) d = 1，后三位可以取到yyy=000~efg，共efg+1次数；

   (2.3) d > 1，后三位可以取到yyy=000~999，共1000次数

把所有情况加到一起就是1出现在第4位上的次数。时间复杂度$1028*10=1600$，（0~9十个数，计算2个count()，数字共8位，）。考虑一些边界情况：所求数字在第一位出现的次数——没有情况1；求0在某一位出现的次数，如在第4位，前三位abc不能取000，既不能有前导0，即000123不是一个合法的写法，应直接写成是123，这样就不会有0的次数了。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10;

/*

001~abc-1, 999

abc
    1. num[i] < x, 0
    2. num[i] == x, 0~efg
    3. num[i] > x, 0~999

*/

int get(vector<int> num, int l, int r)    //取出num中从l到r位的数字
{
    int res = 0;
    for (int i = l; i >= r; i -- ) res = res * 10 + num[i];
    return res;
}

int power10(int x)   //求10的x次方
{
    int res = 1;
    while (x -- ) res *= 10;
    return res;
}

int count(int n, int x)
{
    if (!n) return 0;

    vector<int> num;
    while (n)
    {
        num.push_back(n % 10);    //将n的每一位存入vector num
        n /= 10;
    }
    n = num.size();

    int res = 0;
    for (int i = n - 1 - !x; i >= 0; i -- )
    {
        if (i < n - 1)
        {
            res += get(num, n - 1, i + 1) * power10(i);
            if (!x) res -= power10(i);    //若x是0，则有去掉前几位都是0的情况
        }

        if (num[i] == x) res += get(num, i - 1, 0) + 1;
        else if (num[i] > x) res += power10(i);
    }

    return res;
}

int main()
{
    int a, b;
    while (cin >> a >> b , a)
    {
        if (a > b) swap(a, b);

        for (int i = 0; i <= 9; i ++ )
            cout << count(b, i) - count(a - 1, i) << ' ';
        cout << endl;
    }

    return 0;
}

3.状态压缩DP

例题1：蒙德里安的梦想（Acwing 291）

求把$NM$的棋盘分割成若干个12的的长方形，有多少种方案。例如当N=2，M=4时，共有5种方案。当N=2，M=3时，共有3种方案。如下图所示：

数据范围：$1≤N,M≤11$

上面的问题可以理解为：在下面$1*1$的网格中，我们把所有的横向长方形放完之后，纵向长方形的摆放只有一个方案，因此问题总的方案数就等于摆放横着的小长方形的方案数。

我们可以按列来求，每一列用一个状态f[i,j]来表示，第i列，上一列“伸出”的小长方形的行的状态用j表示，用二进制表示状态数，如共有5行，那j的状态数就是$0 \sim 31$，即j表示上一列有哪些行“伸出”了小长方形，如下图所示$j=(10010)_2$。

若当前要算的状态是第i列的j=00001，前一列k=10010，这两列伸出的小长方形不能冲突，即(j & k) == 0，第i-1列所有空白行的个数必须是偶数，因为我们枚举完第i列后，第i-1列剩下的空白必须要用竖着的小长方形来填，其长度为2，因此j | k（j 或k ）不能有连续奇数个0，可以先预处理出来。

状态转移方程：f[i,j] += f(i - 1, k)，时间复杂度：$2 \times 2^{11} \times 2^{11}=4 \times 10^7 $， 满足要求。

用二进制去表示状态，是个思维上的难点。

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

using namespace std;

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

int n, m;  // 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 ++)   //预处理单列中所有状态是不是存在连续奇数个0，即摆放完横的了，还能不能再摆竖的
        {
            int cnt = 0;    // cnt 表示单列中连续一段的0的个数
            st[i] = true;
            for(int j = 0; j < n; j ++)
                if(i >> j & 1)    //若当前这一位是1，说明这一段中横着的已经放好了，就判断一下上一段中是否有奇数个0
                {
                    if(cnt & 1)  st[i] = false;   // 如果cnt是奇数，则不行
                    cnt = 0;   // 遇到1了，说明连续一段结束了，cnt 归为0
                }
                else cnt ++;
            if (cnt & 1)  st[i] = false;   // 最后再判断一下最后一段的个数
        }
        
        memset(f, 0, sizeof f);
        f[0][0] = 1;    // 第一列，只有j是0时，才有一种方案
        for(int i = 1; i <= m; i ++)   //枚举第i列
            for(int j = 0; j < 1 << n; j ++)    //枚举第i列的所有状态
                for(int k = 0; k < 1 << n; k ++)    //枚举第i - 1列的所有状态
                    if((j & k) == 0 && st[j | k])   //如果j与上k=0，且j|k不存在连续奇数个0
                        f[i][j] += f[i - 1][k];     //状态转移方程
                        
        cout << f[m][0] << endl;   //第m-1列必须没有“伸出”任何横着的小长方形，即f[m][0]就是所求方案数
    }
    
    return 0;
}

例题2：最短Hamilton路径

给定一张$ n $个点的带权无向图，点从$ 0 \sim n-1$标号，求起点$ 0 $到终点$ n-1 $的最短Hamilton路径。 Hamilton路径的定义是从$ 0 $到$ n-1 $不重不漏地经过每个点恰好一次。

输入格式：第一行输入整数n。接下来n行每行n个整数，其中第$i$行第$j$个整数表示点$i$到$j$的距离（记为$a[i,j]$）。对于任意的x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。

数据范围：$1≤n≤20, 0≤a[i,j]≤10^7$

暴力做法：枚举要走的点的顺序，$n!$；再求路径的长度，$n$；时间复杂度就是$20!*20$，大概有20位数字，肯定不满足要求了。考虑用状态压缩DP来做：

• 状态表示f[i,j]：
  • 集合：所有从0走到j，走过的所有点是i的所有路径；走过的点存在i之中，用二进制数表示所有点的状态
  • 属性：MIn，求最短Hamilton路径
• 状态计算：
  • 集合划分：以倒数第二个点来分类，分为倒数第二个点是$0,1,2,\dots,n-1$；设倒数第二个值为$k$，a[k][j]表示点k到点j的距离，从0走到点k的所有点就等于从0走到点j的所有点减去点j，即i-{j}；
  • 则状态转移方程为：f[i,j]=min(f[i,j], f[i-{j}, k]) + a[k][j]，$k=0,1,2\dots,n-1$

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

using namespace std;

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

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 i = 0; i < 1 << n; i ++)   //枚举所有点有没有被经过的状态
        for(int j = 0; j < n; j ++)    //枚举路径中最后一个点
            if(i >> j & 1)             //如果i的二进制表示中的第j位是1，即当前路径中经过了j
                for(int k = 0; k < n; k ++)      //枚举路径中倒数第二个点
                    if((i - (1 << j)) >> k & 1)  //如果当前路径经过的点的状态减去点j的状态，即从0到倒数第二个点的路径中有经过点k
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);    //则可以状态转移
    cout << f[(1 << n) - 1][n - 1] << endl;      //最后应该输出从0到点n-1，且所有点都有经过的路径的最短长度
    return 0;
}

4.树形DP

例题：没有上司的舞会（Acwing 285）

Ural大学有N名职员，编号为1~N。他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。每个职员有一个快乐指数，用整数$ H_i $给出，其中$ 1≤i≤N$。现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式：第一行一个整数$N$。接下来$N$行，第$ i $行表示$ i $号职员的快乐指数$H_i$。接下来$N-1$行，每行输入一对整数$L, K$,表示$K$是$L$的直接上司。

输出格式：输出最大的快乐指数。

数据范围：$1≤N≤6000,−128≤H_i≤127$

• 状态表示：

  • 集合：f[u,0]表示所有从以u为根的子树中选择，并且不选u这个点的方案；f[u,1]表示所有从以u为根的子树中选，并且选择u这个点的方案；
  • 属性：Max，求方案中点值之和的最大值

• 状态计算：

  • 对于f[u,0]，不选点u，则其孩子节点可以选或者不选，则$f[u,0]=\sum \max(f[s_i,0], f[s_i,1])$；

  • 对于f[u,1]，选了点u，则其孩子节点不可以选，则$f[u,1]=\sum \max(f[s_i,0])+h_u$

  • 时间复杂度：每个状态在计算时要枚举它的孩子节点，所以节点的孩子的总数就是树中边的个数，即$n-1$，因此时间复杂度为$O(n)$

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

const int N = 6010;

int n;
int happy[N];
int h[N], e[N], ne[N], idx;   //用邻接表存树
int f[N][2];
bool has_father[N];    //本题中没有告诉根节点是谁，需要自己判断，根节点即是没有父节点的点

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u)    //递归
{
    f[u][1] = happy[u];
    
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];   // j是u的某一个子节点
        dfs(j);
        
        f[u][0] += max(f[j][0], f[j][1]);
        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);
    for(int i = 0; i < n - 1; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        has_father[a] = true;   // b是a的父节点
        add(b, a);
    }
    
    int root = 1;
    while(has_father[root])  root ++;  //没有父节点的就是根节点
    
    dfs(root);
    
    printf("%d\n", max(f[root][0], f[root][1]));
    
    return 0;
}

5. 记忆化搜索

前面求解每种状态是用到了循环，这个题来看一下怎么用递归的方法来做DP问题。

给定一个R行C列的矩阵，表示一个矩形网格滑雪场。矩阵中第$ i $行第$ j $列的点表示滑雪场的第$ i $行第$j $列区域的高度。一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

下面给出一个矩阵作为例子：

在给定矩阵中，一条可行的滑行轨迹为24-17-2-1。在给定矩阵中，最长的滑行轨迹为25-24-23-…-3-2-1，沿途共经过25个区域。现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成最长滑雪轨迹，并输出其长度(可经过最大区域数)。

数据范围：$1≤R,C≤300,0≤$矩阵中整数$≤10000$。

• 状态表示f[i.j]：

  • 集合：f[i,j]表示所有从$(i,j)$开始滑的路径
  • 属性：Max

• 状态计算：

  • 集合划分：把f[i,j]的所有路径分为四类：向上，下，左，右滑，f[i,j]应等于四类取值的最大值；当然每一类并不一定存在，需要其高度低于当前点的高度。（图必须是拓扑图，即不存在环，本题的状态中显然是不存在环的，因为高度递减，一定是无环的。

记忆化搜索的好处是“代码复杂度”低，思路简单，代码好写。

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

const int N = 310;

int n, m;
int h[N][N];
int f[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};   //上、右、下、左

int dp(int x, int y)
{
    int &v = f[x][y];   // 引用
    if(v != -1)  return v;   // 如果dp(x,y)已经算过了，就直接返回其值就行
    
    v = 1;   // v的最小值是1
    for(int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a >=1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y])
            v = max(v, dp(a, b) + 1);
    }
    
    return v;
}

int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            scanf("%d", &h[i][j]);
            
    memset(f, -1, sizeof f);
    
    int res = 0;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            res = max(res, dp(i, j));
    
    printf("%d\n", res);
    
    return 0;
}