校招真题练习034 倒水(贝壳)

题目描述
要把m升的水倒入n个相同的容器中（假设容器足够大），允许有的容量是空的，问共有多少种不同的倒法？（用k表示）5，1，1和1，5，1和1，1，5是同一种倒法。

输入描述:
第一行是测试数据的数目x(0≤x≤20)。以下每行均包含二个整数m和n，以空格分开。1≤m，n≤10。

输出描述:
对输入的每行数据m和n，用一行输出相应的k。

 1 def func(m,n):
 2     if m == 1 or m == 0:
 3         return 1
 4     elif n == 1:
 5         return 1
 6     else:
 7         if n > m:
 8             n = m
 9         count = 0
10         for i in range(1,n+1):
11             if i == 1:
12                 count += func(m,i)
13             else:
14                 count += func(m-i,i)
15         return count
16 
17 def main():
18     s = int(input())
19     for i in range(s):
20         m,n = map(int,input().split())
21         print(func(m,n))
22 
23 
24 if __name__ == '__main__':
25     main()

算法思路：动态规划。