递归or动态规划 | HJ61 放苹果

# 最优解1：递归
def solution(m, n):
    # 如果没有苹果或只有1个苹果，则方案数返回1；如果只有一个盘子，剩下苹果必须全放盘里，也只剩一种方案
    if m == 0 or m == 1 or n == 1: 
        return 1
    # 如果盘子数量多于苹果，说明必定有n-m个盘子会空着，必定的事情不会影响方案数
    elif n > m:                                     
        return solution(m, m)
    else: # 如果苹果多于盘子，盘子空一个，则要递归(m,n-1)；不空，则所有盘子都至少放一个苹果(m-n,n)
        return solution(m, n-1) + solution(m-n, n)
    return
     
while True:
    try:
        m, n = map(int, input().split())
        print(solution(m, n))
    except:
        break

# 最优解2：动态规划
def solution(m, n):
    dp = [[0 for i in range(n+1)] for j in range(m+1)]
    for i in range(m+1):
        dp[i][1] = 1  # 如果只有一个盘子则只有一种放置方案
    for j in range(1, n+1):
        dp[0][j] = 1  # 如果没有苹果则只有一种放置方案
        dp[1][j] = 1  # 如果只有一个苹果也相当于只有一种方案
    for i in range(2, m+1):
        for j in range(2, n+1):
            if i < j: # 如果苹果数量少，则盘子一定会空，所以去除那些空的盘子其实不影响方案数
                dp[i][j] = dp[i][i]
            else:  # 如果苹果数量多，则考虑是否要装够j个盘子，如果不装够则有dp[i][j-1]，如果装够则相当于从所有盘子同时去掉一个苹果无影响，则有dp[i-j][j]
                dp[i][j] = dp[i-j][j] + dp[i][j-1]
     
    return dp[m][n]
     
while True:
    try:
        m, n = map(int, input().split())
        print(solution(m, n))
    except:
        break

# 我的代码（超时不通过）
import copy
def func(apples, plates):
    if not apples:
        tmp = sorted(copy.deepcopy(plates))
        if tmp not in res:
            res.append(tmp)
        return 
    for i in range(len(plates)):
        plates[i] += 1
        func(apples-1, plates)
        plates[i] -= 1

a, p = list(map(int, input().split()))
plates = [0] * p
res = []
func(a, plates)
print(len(res))

用时：40min