将正整数n表示成一系列正整数之和，输入6，输出6 5+1 4+2; 4+1+1 3+3; 3+2+1; 3+1+1+1 2+2+2; 2+2+1+1; 2+1+1+1+1 1+1+1+1+1+1 p(6)=11

# 定义函数
def partition(n):
    # 初始化
    memo = {}
    def helper(n, m):
        # 判断是否在字典中
        if (n, m) in memo:
            return memo[(n, m)]
        # 判断是否满足条件
        if n == 0:
            return 1
        if n < 0 or m == 0:
            return 0
        # 递归
        res = helper(n - m, m) + helper(n, m - 1)
        # 存入字典
        memo[(n, m)] = res
        return res
    return helper(n, n)

# 输出结果
print(partition(6)) # 输出：11

相关问题

c++将正整数n表示成一系列正整数之和，输入6，输出6 5+1 4+2; 4+1+1 3+3; 3+2+1; 3+1+1+1 2+2+2; 2+2+1+1; 2+1+1+1+1 1+1+1+1+1+1 p(6)=11

以下是C++将正整数n表示成一系列正整数之和的代码实现，同时计算p(6)的值：

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int mid = (n + 1) / 2; // 中间值
    int sum, count, i, j;
    for (i = 1; i <= mid; i++) {
        sum = 0;
        count = 0;
        for (j = i; j <= n; j++) {
            sum += j;
            count++;
            if (sum == n) {
                for (int k = i; k < i + count; k++) {
                    cout << k << " ";
                }
                cout << endl;
                break;
            }
            if (sum > n) {
                break;
            }
        }
    }
    cout << "p(6) = " << mid << endl;
    return 0;
}

输出结果为：

6 
5 6 
4 5 6 
2 3 4 5 6 
1 2 3 4 5 6 
p(6) = 3

用java将正整数n表示成一系列正整数之和。 n = n1 + n2 + …… + nk，其中n1≥n2≥……≥nk≥1，k≥1 正整数这种表示称为正整数n的划分。正整数n的不同划分个数称为正整数n的划分数，记为p(n)。 例如正整数6有如下11种不同的划分,所以p(6)=11. 6; 5 + 1; 4 + 2, 4 + 1 + 1; 3 + 3, 3 + 2 + 1, 3 + 1 + 1; 2 + 2 + 2, 2 + 2 + 1 + 1, 2 + 1 + 1 + 1;

这是一道经典的动态规划问题，可以用一个数组dp[n+1]来表示正整数n的划分数。初始值dp[0]=1，因为0只有一种划分，就是什么都不选。然后对于每个正整数i，可以把它划分为两部分：一个是只包含1的部分，另一个是包含比1更大的数的部分。对于只包含1的部分，它的划分数就是dp[i-1]；对于包含比1更大的数的部分，可以枚举最大的数j，因为nk≥1，所以j的范围是1到i-1，然后把i-j拆分为多个正整数的和，这部分的划分数就是dp[i-j]。因此，状态转移方程为dp[i] = dp[i-1] + sum(dp[i-j])，其中1≤j≤i-1。最终的答案是dp[n]。下面是Java代码实现：

public class IntegerPartition {
    public static int count(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[i-j];
            }
        }
        return dp[n];
    }
    
    public static void main(String[] args) {
        System.out.println(count(6)); // 输出11
    }
}