题解 | #放苹果#

动态规划解法，复杂度O(mn)

while True:
    try:
        apple, plate= list(map(int, input().split()))
        ans_array = [[1 for i in range(11)] for j in range(10)]
        for i in range(2, len(ans_array[1])):
            ans_array[1][i] = i // 2 + 1
        for i in range(2, len(ans_array)):  # i+1为盘子数
            for j in range(2, 11):  # j为苹果数
                if i+1 > j:
                    ans_array[i][j] = ans_array[i-1][j]
                elif i+1 == j or i+2 == j:
                    ans_array[i][j] = ans_array[i-1][j] + 1
                else:
                    ans_array[i][j] = ans_array[i-1][j] + ans_array[i][j-i-1]
        print(ans_array[plate-1][apple])
    except EOFError:
        break