【笔试算法】正整数划分

正整数划分

例题

将正整数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∑m​q(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∑m​q(n,m)

则有

1. 首先当n=0：return 1:表示已经被分完

2. m=0:则无法实现，即return 0

3. 当m=1 or n=1：则return 1
   n=1:则由1组成
   m=1：则由n个1组成这两种情况都是一种方式

4. 当n < m 则：s(n,m)=s(n,n) ：没那么多正整数分 所以转换为s(n, n)

5. 当n=m ：s(n,m)= 1 + s(n, m-1)：正整数n的划分由直接全分为1这一种情况和
   分为m-1种的划分组成
   即：$$\begin{gathered} ifm=n \\ s(n,m)=q(n,m)+s(n,m-1)=1+s(n,m-1) \end{gathered}$$

6. n>m>1: s(n,m)=s(n,m-1)+s(n-m,m)
   重要：
   $$\begin{gathered} s(n,m)=q(n,m)+s(n,m-1) \\ =s(n,m-1)+s(n-m,m) \end{gathered}$$
   n要被分成m个， 此时，确定有m个1在等待分配， 余下的值为 n - m，那么将n-m分配给m个数有多少种分法，即是这题所求的 s(n-m, m)。故上等式成立

Python 实现

递归法（直观但复杂）

def dfs(n,m):if n==0:return 1elif m==0:return 0elif n==1 or m==1:return 1elif n<m:return dfs(n,n)elif n==m:return dfs(n,m-1)+1else: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 1for 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]

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！