正整数划分
例题
将正整数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
思路
令q(n, m)为正整数n被分成m个数的划分数，比如q(5, 3) = 2 即是【3+1+1, 2+2+1】，则这个题求的就是 ∑ i = 1 m q ( n , m ) \sum_{i=1}^{m}q(n , m) i=1∑mq(n,m)则令 s ( n , m ) = ∑ i = 1 m q ( n , m ) s(n , m) = \sum_{i=1}^{m}q(n , m) s(n,m)=i=1∑mq(n,m)
则有
- 首先当n=0：return 1:表示已经被分完
- m=0:则无法实现，即return 0
- 当m=1 or n=1：则return 1
n=1:则由1组成
m=1：则由n个1组成这两种情况都是一种方式 - 当n < m 则：s(n,m)=s(n,n) ：没那么多正整数分 所以转换为s(n, n)
- 当n=m ：s(n,m)= 1 + s(n, m-1)：正整数n的划分由直接全分为1这一种情况和
分为m-1种的划分组成
即： i f m = n s ( n , m ) = q ( n , m ) + s ( n , m − 1 ) = 1 + s ( n , m − 1 ) if\quad m = n\newline s(n , m) = q(n , m) + s(n, m -1)=1+ s(n, m -1) ifm=ns(n,m)=q(n,m)+s(n,m−1)=1+s(n,m−1) - n>m>1: s(n,m)=s(n,m-1)+s(n-m,m)
重要：
s ( n , m ) = q ( n , m ) + s ( n , m − 1 ) = s ( n , m − 1 ) + s ( n − m , m ) s(n , m) = q(n , m) + s(n, m -1)\newline =s(n, m -1) +s(n-m, m) s(n,m)=q(n,m)+s(n,m−1)=s(n,m−1)+s(n−m,m)
n要被分成m个， 此时，确定有m个1在等待分配， 余下的值为 n - m，那么将n-m分配给m个数有多少种分法，即是这题所求的 s(n-m, m)。故上等式成立
Python 实现
递归法（直观但复杂）
def dfs(n,m): if n==0: return 1 elif m==0: return 0 elif n==1 or m==1: return 1 elif n<m: return dfs(n,n) elif n==m: return dfs(n,m-1)+1 else: return dfs(n,m-1)+dfs(n-m,m) 讯享网
动态规划法
讯享网def s(n, m): dp = [[0 for i in range(n + 1)] for j in range(n + 1)] dp[0][0] = 1 # 当n=0：return 1 for i in range(1, n + 1): for j in range(1, n + 1): # 此时 i 就是 n， j 就是 m，从s（1 ，1）开始算累加到所需要的值 if i < j: dp[i][j] = dp[i][i] # 当n < m ：s(n,m)=s(n,n) if i == j: dp[i][j] = 1 + dp[i][j - 1] # 当 n = m ：s(n,m)= 1 + s(n, m-1) if i > j: dp[i][j] = dp[i][j - 1] + dp[i - j][j] # n>m>1: s(n,m)=s(n,m-1)+s(n-m,m) if i == n and j == m: return dp[i][j]
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/54628.html