牛客华为HJ61放苹果

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 这种 递推公式的 问题，最关键的就是明确 每一项的定义！
# 定义： d[m][n] 是 m个苹果 在 n个盘子中的 所有放法；
#  d[m][n-1] 就是 m个苹果 在 n-1个盘子中 的所有放法； 
m , n = map(int,input().split(' '))

# 初始化,d[0][i] = 0 d[i][0] = 0 
d = [[0 for _ in range(n+1)] for _ in range(m+1)]
result = 0
    # 因为 递推公式是  由 小的推到到大的，所以遍历 方向也是从小到大；
    # 苹果多或者等于盘子 分 有空 和无空 两种情况， 一种确保一个空位然后剩下位置随便放，保证有空；另一种先每盘子放一个再随便放，保证不空。
    # 苹果少于盘子，那减去一个盘子 还是一样的；
for i in range(0,m+1):
    for j in range(1,n+1):
        # print(i,j)
        if i==0 or i==1 or j==1:
            d[i][j] = 1             # 初始化
        elif i>=j:
            d[i][j] = d[i][j-1] + d[i-j][j]                                      
        else:
            d[i][j] = d[i][j-1]
        result = d[i][j]
print(result)