题解 | #放苹果#

m , n = map(int,input().split())

a = [[0]*(n+1) for _ in range(m+1)]

for j in range(1,n+1):
    a[1][j] = 1
    a[0][j] =1

for i in range(1,m+1):
    a[i][1] = 1

for i in range(2,m+1):
    for j in range(2,n+1):
        if i<j:
            #至少存在一个空盘
            a[i][j] = a[i][j-1]
        else:
            #至少存在一个空盘a[i][j-1]
            #没有空盘 a[i-j][j]
            a[i][j] = a[i][j-1]+a[i-j][j]

print(a[m][n])
"""
好多人问为啥没管 5 1 1 和 1 5 1
不用管
5 1 1 本质上是7个果放3个盘的一种场景
但是我们算7个果放3个盘是这样算的 分类讨论
1.存在一个空盘 比如 7 0 0    5 2 0
本质上是7个果放2个盘再加一个0盘  = a[i][j-1]
2.不存在一个空盘 比如5 1 1 
相当于是 1 1 1 上再分配4 = 7-3个苹果 = 4个果分3个盘的情况 = a[i-j][j]

我们默认4个果3个盘是动态规划中已经到达过的节点,
所以4个果3个盘的分配中 不存在 4 0 0  和 0 4 0 两种 
所以4个果分3个盘 衍生出来的不存在一个空盘的7个果放3个盘场景也就不会有 5 1 1 和 1 5 1

"""