动态规划#HJ61 放苹果

题目分析

1. 苹果数m，盘子数n
2. 允许空盘，与顺序无关

思路

1、递归目的:

最终结果是要返回solution(m,n)

2、递归退出条件

a. 没有苹果：m=0，每个盘子都不能放置，只有这1种情况。

b. 只有1个苹果：m=1，放在哪个盘子都只是1种情况。

c. 只有1个盘子：n=1，此时剩余苹果只能放在这个盘子里，只有这1种情况。

3、中间情况的递归

a. 苹果数量少于盘子数量：m<n

此时盘子比苹果多n-m个，不论怎么放置，最多放满n个盘子中的m个盘子。
实际上，相当于考虑在m个盘子里的放置m个苹果的情况。
此时，m<n时，相当于`solution(m, m)`

b. 苹果数量大于等于盘子数量： m≥n，此时有独立出现的2种情况。

• 如果要空一个盘子，则相当于m个苹果放在n-1个盘子里。 此时，相当于solution(m, n-1)
• 如果不空盘子，相当于每个盘子里先放一个苹果，相当于都没放。 此时考虑剩下的m-n个苹果在n个盘子里放置的情况。 此时，相当于solution(m-n, n)
• 综上，m≥n时，相当于solution(m, n-1)+solution(m-n, n)

4、翻译——转移方程

• 动态规划数组dp[i][j]为m个苹果n个盘子的放置方案数

• 苹果数量少于盘子数量：m<n：此时，相当于solution(m, m) 即dp[i][j]=dp[i][i]
• 苹果数量大于等于盘子数量： m≥n，此时有独立出现的2种情况，相当于solution(m, n-1)+solution(m-n, n)。 即dp[i][j]=dp[i][j-1]+dp[i-j][j]

python代码

def solution(m,n):
    dp = [[0 for i in range(n+1)] for j in range(m+1)] #1.建立mxn的二维数组
    #2.输入三种退出条件
    for j in range(1,n+1):
        dp[0][j] = 1 #a.没有苹果：m=0，每个盘子都不能放置，只有这1种情况。
        dp[1][j] = 1 #b.只有1个苹果：m=1，放在哪个盘子都只是1种情况。
    for i in range(m+1):
        dp[i][1] = 1 #c.只有1个盘子,此时剩余苹果只能放在这个盘子里，只有这1种情况。
    #3.中间情况的递归
    for i in range(2,m+1):
        for j in range(2,n+1):
            if i < j: dp[i][j] = dp[i][i] #a.m<n时，相当于solution(m, m)
            else: dp[i][j] = dp[i-j][j] + dp[i][j-1] #m≥n时，相当于solution(m, n-1)+solution(m-n, n)
    return[m][n] #最终返回m,n位置的值

while True:
    try:
        m, n = map(int, input().split()) #输入m n
        print(solution(m, n))
    except:
        break

图片说明