[已解决]Python求助：复杂的整数划分问题

isdkz

1. # coding: utf-8
   
2. 
   
3. def split_n_k(n, k):
   
4.     """
   
5.     将正整数 n 划分成 k 个正整数之和的划分数目
   
6.     """
   
7.     if n < k:
   
8.         return 0
   
9.     if n == k:
   
10.         return 1
    
11.     # 动态规划
    
12.     dp = [[0] * (n + 1) for _ in range(k + 1)]
    
13.     for i in range(1, k + 1):
    
14.         for j in range(i, n + 1):
    
15.             if i == 1:
    
16.                 dp[i][j] = 1
    
17.             else:
    
18.                 dp[i][j] = dp[i - 1][j - i] + dp[i][j - i]
    
19.     return dp[k][n]
    
20. 
    
21. 
    
22. def split_diff(n):
    
23.     """
    
24.     将正整数 n 划分成若干个不同正整数之和的划分数目
    
25.     """
    
26.     dp = [0] * (n + 1)
    
27.     dp[0] = 1
    
28.     for i in range(1, n + 1):
    
29.         for j in range(n, i - 1, -1):
    
30.             dp[j] += dp[j - i]
    
31.     return dp[n]
    
32. 
    
33. 
    
34. def split_odd(n):
    
35.     """
    
36.     将正整数 n 划分成若干个奇正整数之和的划分数目
    
37.     """
    
38.     # 这里的代码和上面的 split_diff 函数也很相似
    
39.     dp = [0] * (n + 1)
    
40.     dp[0] = 1
    
41.     for i in range(1, n + 1, 2):
    
42.         for j in range(i, n + 1):
    
43.             dp[j] += dp[j - i]
    
44.     return dp[n]
    
45. 
    
46. 
    
47. while True:
    
48.     try:
    
49.         n, k = map(int, input().split())
    
50.         print(split_n_k(n, k))
    
51.         print(split_diff(n))
    
52.         print(split_odd(n))
    
53.     except:
    
54.         break
    

复制代码