计数类DP

HYLW · 2024-01-25 09:54:21 · 算法·理论

返回母本《动态规划》

1.计数类DP简介

大部分的DP问题会要求求一个最值，而还有一部分DP问要求求一个方案数，这就是计数类DP，它仍然没有实质性的内涵。

2.整数划分

题目：

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

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

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

• 输入格式

共一行，包含一个整数 n。

• 输出格式

共一行，包含一个整数，表示总划分数量。

由于答案可能很大，输出结果请对 10^9+7 取模。

• 数据范围

• 输入样例:

5

• 输出样例：

7

• 解：

首先统一一下细节：

• 有取模，还不小，不开long long见祖宗。
• 划分的 \{n_i\} 是有序的。

接着，贪一下，贪不了，好，是DP。

然而这道题可以从多种角度考虑，这里先从背包的角度思考：

我们把 n_i 的值当作体积，n_i 就是一个物品，n 就是背包，其值即总体积，设f[i][j]表示前 i 个物品总体积恰好是 j 的方案数，易得

f[i][j]=f[i-1][j]+\sum\limits_{k=1}^{k\times v[i] \leq j}(f[i-1][j-k\cdot v[i]])

由于：

f[i][j-v[i]]=f[i-1][j-v[i]]+\sum\limits_{k=2}^{k\times v[i] \leq j}(f[i-1][j-k\cdot v[i]])=\sum\limits_{k=1}^{k\times v[i] \leq j}(f[i-1][j-k\cdot v[i]])

化简得：

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

再来个降维优化：

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

注意初始化，f[0]=1;

那么，

Theory is feasible, practice begins.

：

#include<bits/stdc++.h>
using namespace std;
const int N=1010,mod=1e9+7;
int n;
int f[N];
int main(){
    scanf("%d",&n);
    f[0]=1;

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

    printf("%d",f[n]);
    return 0;
}

其他方法，都是二维角度构建状态，并设置适宜的状态转移方程，这也是DP问题的核心素养，可以看看。

返回母本《动态规划》