题解 | #放苹果#

#使用递归思想将大问题划分为小问题递归迭代求解或用动态规划解决重叠子问题


#递归，避免重复计算，用记忆化技术优化递归
def initialized_memo(m,n):
    return [[0]*(n+1) for _ in range(m+1)]
max_m = 10
max_n = 10
memo = initialized_memo(max_m,max_n)
def count_recursive(m,n):
    if m < 0 or n < 0:
        return 0
    elif m == 1 or n == 1:
        return 1
    elif memo[m][n] != 0:
        return memo[m][n]
    count = count_recursive(m,n-1)+count_recursive(m-n,n)#一个盘子为空或全部都有果子
    memo[m][n] = count
    return count

m,n = input().split()
print(count_recursive(int(m),int(n)))

利用memorial recursion策略，初始化一个二维数组全为0，用m和n，苹果数量和盘子数量作为索引来取memo[m][n],第一列的索引为0，这列取不到，因为m∈[0,10],n∈[1,10],每次调用自身并且更新memo[m][n]