解题思路

这个问题可以转化为一个动态规划问题。与完全背包问题不同，完全背包中每个物品可以选多次，而本题中每个数字只能选一次（因为要求严格递减），因此更类似于01背包问题。

动态规划方法

定义dp[i][j]表示使用前i个数字（1到i）组成和为j的方案数。状态转移方程为：

• 如果不选数字i，则方案数为dp[i-1][j]
• 如果选数字i，则方案数为dp[i-1][j-i]（因为每个数字只能选一次）
• 因此dp[i][j] = dp[i-1][j] + dp[i-1][j-i]

初始化条件：dp[0][0] = 1

最终答案为dp[n-1][n]

与完全背包的区别

1. 完全背包中物品可以无限次选取，而本题每个数字只能选一次
2. 完全背包的状态转移是dp[i][j] = dp[i-1][j] + dp[i][j-w[i]]，而本题是dp[i][j] = dp[i-1][j] + dp[i-1][j-i]

复杂度分析

• 时间复杂度：$O(n^2)$，因为需要填充一个$n×n$的二维表格
• 空间复杂度：$O(n^2)$

代码实现

Python代码

n = int(input())

# 初始化二维DP数组
dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1  # 初始条件

for i in range(1, n + 1):  # 考虑数字1到n
    for j in range(n + 1):  # 计算组成0到n的方案数
        dp[i][j] = dp[i - 1][j]  # 不选数字i的方案数
        if j >= i:
            dp[i][j] = dp[i][j] + dp[i - 1][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();
        long[][] dp = new long[n + 1][n + 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 - 1][j - i]; // 选数字i的方案数
                }
            }
        }
        
        System.out.println(dp[n][n]);
    }
}

C++代码

#include <iostream>
#include <vector>

using namespace std;
#define ll long long
int main() {
    int n;
    cin >> n;
    vector<vector<ll>> dp(n + 1, vector<ll>(n + 1, 0));
    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 - 1][j - i]; // 选数字i的方案数
            }
        }
    }
    
    cout << dp[n][n] << endl;
    return 0;
}

题目描述：

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

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

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

输入

共一行，包含一个整数$n$。$1<=n<=500$

输出

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

示例1

输入：

4

输出：

2

提示

示例$1$一共2种:

$4$

$3+1$

示例2

输入：

6

输出：

4

提示

示例$2$一共4种:

$6$

$5+1$

$4+2$

$3+2+1$