问题分析

题目要求求出正整数 n 的划分方式数目。我们需要找出 n 可以拆分成若干个正整数的不同方法，并且这些整数满足非递增的条件。例如，4 可以拆分成以下五种方式：

• 4
• 3 + 1
• 2 + 2
• 2 + 1 + 1
• 1 + 1 + 1 + 1

这种划分问题可以通过动态规划解决。

状态定义

设 dp[i][j] 表示从 1 到 i 的数中，划分出和为 j 的不同方式数目，且满足划分中的每个数都不小于上一个数。

状态转移方程

1. 如果我们不使用数 i，那么答案就和 dp[i-1][j] 相同。
2. 如果我们使用数 i，那么我们需要在 dp[i][j-i] 的基础上加上一个 i。

因此，状态转移方程为：

• dp[i-1][j] 表示不使用当前数 i。
• dp[i][j-i] 表示使用当前数 i。

初始化

• dp[0][0] = 1，表示和为 0 的方式有 1 种，即不选择任何数。
• 其他的 dp[0][j] 为 0，表示没有数可以组合成非零的和。

最终答案

最后的答案即为 dp[n][n]，表示从 1 到 n 的数，和为 n 的划分方法数。

Python 代码

# 输入
n = int(input())

# 创建一个 (n+1) x (n+1) 的 dp 表
dp = [[0] * (n + 1) for _ in range(n + 1)]

# 初始化 dp[0][0] = 1
dp[0][0] = 1

# 动态规划求解
for i in range(1, n + 1):
    for j in range(0, n + 1):
        dp[i][j] = dp[i - 1][j]  # 不使用当前数 i
        if j >= i:
            dp[i][j] = dp[i][j] + dp[i][j - i]  # 使用当前数 i

# 输出结果
print(dp[n][n])

java 代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 创建一个 (n+1) x (n+1) 的 dp 表
        long[][] dp = new long[n + 1][n + 1];
        
        // 初始化 dp[0][0] = 1
        dp[0][0] = 1;

        // 动态规划求解
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = dp[i - 1][j];  // 不使用当前数 i
                if (j >= i) {
                    dp[i][j] = dp[i][j] + dp[i][j - i];  // 使用当前数 i
                }
            }
        }

        // 输出结果
        System.out.println(dp[n][n]);
    }
}

C++ 代码

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;

    // 创建一个 (n+1) x (n+1) 的 dp 表
    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
    
    // 初始化 dp[0][0] = 1
    dp[0][0] = 1;

    // 动态规划求解
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            dp[i][j] = dp[i - 1][j]; // 不使用当前数 i
            if (j >= i) {
                dp[i][j] = dp[i][j] + dp[i][j - i]; // 使用当前数 i
            }
        }
    }

    // 输出结果
    cout << dp[n][n] << endl;
    
    return 0;
}

题目描述：

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

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

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

输入

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

输出

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

示例

输入：

4

输出：

5

提示

示例$1$一共五种:

$4$

$3+1$

$2+2$

$2+1+1$

$1+1+1+1$