数的划分 python DFS

解题思路:

为了保证不能有重复的，则每位数都要比前一位数相等或者小于前面一位数
例如 对 7 分成 3 份 可以看成a,b,c  --->  a<=b<=c 这样就能保证不会有重复的

对a（也就是第一位数）来说 一共有 7//3 种可能性 也就是 1,2

对b（第二位数）来说 一共有 (7-a)//2-a种可能性 

        a=1    b有 （7-1）//2-a+1 = 3 种可能 --> 1,2,3,

        a=2    b有 （7-2）//2-a+1 = 1 种可能 --> 2

只要a和b确定下来 则c也就可以确定

参考代码：

def DFS(x, k, n):
   if k == 1:
       return 1
   s = 0
   for i in range(x, n // k + 1):  # 能取的数有多少
       s += DFS(i, k - 1, n - i)
   return s


n, k = map(int, input().split())
print(DFS(1, k, n))