题目介绍

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

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

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

方法一 二维完全背包

1.算法细节

• 此题状态表达式和状态方程如何构造？

dp[i][j] 存储 1 ~ i 数字中选择，数量在不超容量前任取，恰好能组成j大小的数的选法总数

• 此题为计数类DP，何以见得判断是计数DP？

正常dp的状态属性：min或者max，而此题所求为cnt方案数量。最基本的一点：最大最小是取最大最小值，而计数DP的方案数量是累增或者累减的类似关系，需要找寻其中自变量和因变量的关系。

• 计数DP的方案数的初始化：与最大最小要往相反的无穷大小赋值不同，计数DP要根据题意所分析，本题在j=0时，显然不论i的大小为何值，都应该是1的方案大小：即不选

• 二维对方案数的优化问题

对去除对方案数的for循环，我们不妨用类似完全背包问题的优化方案去考虑
完全背包问题

f[i , j] =  max( f[i-1,j] , f[i-1,j-v]+w ,  f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max(            f[i-1,j-v]   ,  f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)

整数划分问题
对于能组成j的所有方案，显然应该相等于：取0个i的方案 + 取1个i的方案 + ···· + 取k个i的方案 其中k * i <= j

f[i , j]  =  f[i-1,j] + f[i-1,j-i] + f[i-1,j-2*i] + f[i-1,j-3*i] + .....
f[i , j-i]=             f[i-1,j-i] + f[i-1,j-2*i] + f[i-1,j-3*i] + .....

像完全背包问题的推导过程，我们将两个式子结合：
可得此时状态方程为: f[i][j] = f[i-1][j] + f[i][j-i]

2.具体代码

java

import java.util.*;

public class Main {
    static int N = 1010, n, mod = (int) 1e9 + 7;
    static int f[][] = new int [N][N];

    public static void main(String [] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

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

        for(int i=1; i<=n; i++)
            for(int j=0; j<=n; j++){
                f[i][j] = f[i-1][j];
                if (j >= i)
                    f[i][j] = (f[i-1][j] + f[i][j-i]) % mod;
            }
        System.out.println(f[n][n]);
    }
}

python3

n = int(input())
f = [[0] * (n+10) for i in range(n+10)]
mod = int(1e9 + 7)

for i in range(n+10): f[i][0] = 1

for i in range(1, n+1):
    for j in range(1, n+1):
        f[i][j] = f[i-1][j] % mod
        if j >= i:
            f[i][j] = (f[i][j] + f[i][j - i]) % mod

print(f[n][n])

C++

#include <bits/stdc++.h>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, dp[N][N];

int main(){
    cin >> n;
    for(int i=0; i<=n; i++) dp[i][0] = 1;
    //完全背包二维划分
    for(int i=1; i<=n; i++)
        for(int j=0; j<=n; j++){
            dp[i][j] = dp[i-1][j] % mod;
            if(j >= i)  dp[i][j] = (dp[i-1][j] + dp[i][j-i]) % mod;
        }
    cout << dp[n][n] << endl;
    return 0;
}

方法二 二维完全背包的一维优化

1.算法细节

• 由二维的f[i][j] = f[i-1, j] + f[i][j-i]可以借此优化到一维，完全背包错位依靠的刚好是本位i的状态，而不是01背包问题的i-1所以不需要倒序循环j的大小

此时的状态表达式为f[j]:代表组成j的方案总数,属性为cnt
状态方程化为: f[j] = f[j] + f[j-i]

2.具体代码

java

import java.util.*;

public class Main {
    static int N = 1010, n, mod = (int) 1e9 + 7;
    static int f[] = new int [N];

    public static void main(String [] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

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

        System.out.println(f[n]);
    }
}

python3

n = int(input())
f = [0] * (n+10)
mod = int(1e9 + 7)

f[0] = 1
for i in range(1, n+1):
    for j in range(i, n+1):
            f[j] = (f[j] + f[j - i]) % mod

print(f[n])

C++

#include <bits/stdc++.h>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, dp[N];

int main(){
    cin >> n;
    dp[0] = 1;
    //完全背包二维划分
    for(int i=1; i<=n; i++)
        for(int j=0; j<=n; j++){
            dp[j] = dp[j] % mod;
            if(j >= i)  dp[j] = (dp[j] + dp[j-i]) % mod;
        }
    cout << dp[n] << endl;
    return 0;
}