04117: 简单的整数划分问题

dp，recursion , http://cs101.openjudge.cn/practice/04117

将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。 正整数n 的这种表示称为正整数n 的划分。正整数n 的不同的划分个数称为正整数n 的划分数。

输入

标准的输入包含若干组测试数据。每组测试数据是一个整数N(0 < N <= 50)。

输出

对于每组测试数据，输出N的划分数。

样例输入

5

样例输出

7

提示：5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1

使用动态规划（Dynamic Programming, DP）来求解整数的划分问题。动态规划是一种将复杂问题分解成较小子问题求解的方法。对于整数划分问题，可以定义一个二维的DP数组，其中dp[i][j]表示数字i划分为不超过j的数的划分方式数量。

动态规划状态转移方程可以这样定义：对于dp[i][j]，如果i < j，那么dp[i][j] = dp[i][i]，因为最大的数不能超过i；如果i >= j，那么dp[i][j] = dp[i][j-1] + dp[i-j][j]，这是因为划分数可以分为两部分，一部分是所有划分中不包含j的（即dp[i][j-1]），另一部分是至少包含一个j的，我们从i中去掉一个j，再找剩下的i-j的划分数，因此是dp[i-j][j]。

def partition_count(n):
    # 初始化dp数组，dp[i][j] 表示数字i划分成不超过j的数的划分方式数
    dp = [[0] * (n + 1) for _ in range(n + 1)]

    # 数字0没有实质内容的划分，所以设置dp[0][j]为1
    for j in range(n + 1):
        dp[0][j] = 1

    # 填充dp数组
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i < j:
                dp[i][j] = dp[i][i]
            else:
                dp[i][j] = dp[i][j - 1] + dp[i - j][j]

    # 返回dp[n][n]即为n的划分数
    return dp[n][n]

# 输入处理部分
try:
    while True:
        N = int(input())
        print(partition_count(N))
except EOFError:
    pass

# https://blog.csdn.net/a1097304791/article/details/82915853
'''
记n的m划分的个数为 f(n,m)，即数字 n 可以被划分成不超过 m 的数的划分数。
例如，当n=4时，有5个划分，即{4},{3,1},{2,2},{2,1,1},{1,1,1,1}
注意：4=1+3和4=3+1被认为时同一个划分。
根据n和m的关系，考虑以下几种情况：

(一)当n=1时，无论m的值为多少(m >0)，只有一种划分，即{1}。
(二)当 m=1时，无论n的值为多少，只有一种划分，即n个1，{1,1,1,...,1}。

(三)当 n = m 时，根据划分中是否包含n，可以分为以下两种情况:
(1)划分中包含n的情况，只有一个，即{n}。
(2)划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有(n-1)划分。
因此 f(n,n)=1+f(n,n-1)。

(四)当 n<m 时，由于划分中不可能出现负数，因此就相当于 f(n,n)。

(五)当 n>m 时，根据划分中是否包含最大值m，可以分为以下两种情况:
(1)划分中包含m的情况，即 {m,{x1,x2,.··,xi}}，其中 {x1,x2,...,xi}的和为n-m，
因此这种情况下为f(n-m,m)。
(2)划分中不包含m的情况，则划分中所有值都比m小，即n的(m-1)划分，个数为 f(n,m-1)。
因此f(n,m)=f(n-m,m)+f(n,m-1)。

综上所述：
f(n,m)=1:(n=1|m=1)
f(n,n):(n<m)
1+f(n,m-1):(n=m)
f(n-m,m)+f(n,m-1):(n>m)
'''

def partition_count(n):
    dp = [[0]*(n+1) for _ in range(n+1)]
    
    for i in range(1, n+1):
        dp[i][1] = 1
        dp[1][i] = 1

    
    for i in range(2, n+1):
        for j in range(2, n+1):
            if i > j:
                dp[i][j] = dp[i-j][j] + dp[i][j-1]
            elif i == j:
                dp[i][j] = 1 + dp[i][j-1]
            else:
                dp[i][j] = dp[i][i]
                
    return dp[n][n]


while True:
    try:
        N = int(input())
        result = partition_count(N)
        print(result)
    except EOFError:
        break

思路：简单的整数划分问题【递推+思维】 https://blog.csdn.net/a1097304791/article/details/82915853

这道题的动规思路，下面的论述比较清晰一些：https://www.cnblogs.com/huashanqingzhu/p/7295329.html?utm_source=itdadao&utm_medium=referral

f(n, m) =1; 　　　　　　　　　　 (n=1 or m=1) =f(n, n); 　　　　　　　　 (n<m) =1+ f(n, m-1); 　　 　　 (n=m) =f(n-m,m)+f(n,m-1);　　 (n>m)

recursion

The Python functools module provides a decorator lru_cache which can be used to add a least recently used cache to a function. This can be very useful for recursive functions where the same subproblems are solved multiple times, as it can significantly speed up the function by storing the results of previous computations.

@lru_cache(maxsize=None) is a decorator that adds a cache to the function f. The maxsize argument determines the maximum size of the cache. If maxsize is set to None, the cache can grow without bound.

from functools import lru_cache

@lru_cache(maxsize=None)
def f(n, m):
    if n == 1 or m == 1:
        return 1
    elif n == m:
        return f(n, n - 1) + 1
    elif n < m:
        return f(n, n)
    elif n > m:
        return f(n - m, m) + f(n, m - 1)

while True:
    try:
        n = int(input())
    except EOFError:
        break

    print(f(n, n))

dp：

2020fall-cs101，李博海。OJ04117简单整数划分可以对应到完全背包，OJ04119复杂整数划分的不重复整数可以对应到01背包。当然背包问题求的最大值，而这里求的是“选取物品刚好为n的方法数”。

while True:
    try:
        n = int(input())
    except EOFError:
        break

    dp = [[0]*(n+1) for i in range(n+1)]
    
    for i in range(0, n+1):		# f(n, m) =1, where n=1 or m=1
        dp[i][1] = 1
        dp[0][i] = 1
    
    for i in range(1, n+1):
        for j in range(2, n+1):
            if i >= j:
                dp[i][j] = dp[i][j-1] + dp[i-j][j]
            else:
                dp[i][j] = dp[i][j-1]
    
    print(dp[n][n])

while True:
    try:
        n = int(input())
    except EOFError:
        break

    dp = [[0] * (n + 1) for i in range(n + 1)]

    for i in range(0, n + 1):  # f(n, m) =1, where n=1 or m=1
        dp[i][1] = 1
        dp[0][i] = 1
        dp[1][i] = 1

    for i in range(1, n + 1):
        for j in range(2, n + 1):
            if i >= j:
                dp[i][j] = dp[i][j - 1] + dp[i - j][j]
            else:
                dp[i][j] = dp[i][i]

    print(dp[n][n])

def dp(n,k):
    if n<k:
        return 0
    elif k==1:
        return 1
    elif n<=k+1:
        return 1
    else:
        return dp(n-1,k-1)+dp(n-k,k)

while True:
    try:
        n = int(input())
        cou = 0
        for i in range(1,n+1):
            cou+=dp(n,i)
        print(cou)
    except EOFError:
        break

函数含义

• dp(n,k) 就是计算 pk(n)，即把 n 划分成 k 部分的个数。

各个判断条件对应数学定义

• if n<k: return 0 如果要把 n 划分成比 n 还多的部分（每部分≥1），不可能，返回 0。 ⇒pk(n)=0 当 n<k。

• elif k==1: return 1 把 n 分成 1 部分，只有一种划分：(n)。 ⇒p1(n)=1。

• elif n<=k+1: return 1 例如：n=5,k=4，只能分成 (2,1,1,1)，只有一种。 当 n 很小且接近 k 时，只能有一种划分。

• else: return dp(n-1,k-1)+dp(n-k,k) 这正是题目里给的递推公式：

  pk(n)=pk−1(n−1)+pk(n−k)