两种算法:
1.递归算法:recursion programming
For m apples and n baskets, laying methods==n baskets are laying,remainding apples (m-n) put to n basket+all apples put to (n-1) baskets
Recursing until m==0 or n==1,return 1;
among the reccursion times, if m<0,n<=0,return 0.
对于m个苹果,n个篮子:等于所有篮子都有苹果的放置方法数加上至少一个篮子没有苹果的放置方法数。
往下递归为:(m-n)个苹果放到n个篮子;m个苹果放到(n-1)个篮子;
当初始m<n(下次递归m<0),意味着篮子肯定放不满,所以返回0;
当篮子为n=1,返回1种方法或者苹果数m=0,也返回1种方法,返回1;
迭代至n=0,返回0。
code:
#recursion def putapple(m,n): if m<0 or n==0:return 0 elif m==0 or n==1:return 1 else:return putapple(m-n,n)+putapple(m,n-1) while 1: try: m,n=map(int,input().split()) print(putapple(m,n)) except:break'
2.动态规划算法:dynamic programming
递归为逆向思维,动态规划需要确定放置方法数的动态方程:d[i][j]=d[i][j-1]+d[i-j][j].
动态规划需要确定初始状态:d[0][j]=1;d[1][j]=1;d[i][1]=1.
其中:i个苹果,j个篮子:空篮子的放置方法即可生成至d[m][n].
Recursion is a reversed thinking, but dynamic programming needs to make sure the initial states and the state transition matrix.
生成的二维规划数组(横纵分别为苹果和篮子数,从零开始)为:
0 1 1 1 1 1...
0 1 1 1 1 1...
0 1 2 2 2 2...
0 1 2 3 3 3...
0 1 3 4 5 5...
....................
code:
#dynamic programming def layapples(m,n): dp=[[0 for i in range(n+1)]for j in range(m+1)] #create matrix[m][n],element=0 #boundary condition for i in range(m+1):dp[i][1]=1 #1 basket, one method for j in range(1,n+1): dp[0][j]=1 #0 apple,one method dp[1][j]=1 #1 apple,one method for i in range(2,m+1): #layapple' times array for j in range(2,n+1): if i>=j: #apple num<basket num dp[i][j]=dp[i-j][j]+dp[i][j-1] if i<j: dp[i][j]=dp[i][j-1] #print(dp[i][j]) return dp[m][n] while 1: try: m,n=map(int,input().split()) #layapples(m,n) print(layapples(m,n)) except:break