M01664: 放苹果

dp, dfs, http://cs101.openjudge.cn/practice/01664/

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

输入

第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。

输出

对输入的每组数据M和N，用一行输出相应的K。

样例输入

1
7 3

样例输出

来源

lwx@POJ

将问题转化为动态规划（DP）形式，可以通过构造一个二维DP数组来解决问题，其中 dp[m][n] 表示将m 个苹果放入 n 个盘子的分法数。

状态转移方程

如果没有苹果或者只有一个盘子：
- dp[m][n]=1（基础情况）。
如果盘子数大于苹果数：
- dp[m][n]=dp[m][m]（因为多余的盘子没有意义）。
一般情况下：
- dp[m][n]=dp[m][n−1]+dp[m−n][n]，
- 其中：
  - dp[m][n−1] 表示至少有一个盘子空着的情况。
  - dp[m−n][n] 表示每个盘子至少放一个苹果的情况。

python

def apple_distribution(t, cases):
    # 最大苹果数和盘子数
    max_m = max(c[0] for c in cases)
    max_n = max(c[1] for c in cases)
    
    # 初始化DP数组
    dp = [[0] * (max_n + 1) for _ in range(max_m + 1)]
    
    # 基础情况
    for m in range(max_m + 1):
        dp[m][1] = 1  # 只有一个盘子
    for n in range(max_n + 1):
        dp[0][n] = 1  # 没有苹果
    
    # 填表
    for m in range(1, max_m + 1):
        for n in range(2, max_n + 1):
            if n > m:
                dp[m][n] = dp[m][m]  # 盘子多于苹果
            else:
                dp[m][n] = dp[m][n-1] + dp[m-n][n]
    
    # 处理每个测试用例
    results = []
    for m, n in cases:
        results.append(dp[m][n])
    
    return results

# 主函数
def main():
    t = int(input())  # 测试数据数目
    cases = []
    for _ in range(t):
        m, n = map(int, input().split())
        cases.append((m, n))
    results = apple_distribution(t, cases)
    for res in results:
        print(res)

# 样例测试
if __name__ == "__main__":
    main()

时间复杂度

预处理 DP 表的复杂度为 $O (M \times N)$ ，其中 M,N 是最大苹果数和盘子数。

dfs

python

def count_ways(m, n):
    # 如果只有一个盘子，只能有一种分法
    if n == 1:
        return 1
    # 如果苹果数为0，只有一种分法：所有盘子空
    if m == 0:
        return 1
    # 如果盘子数大于苹果数，最多只需用前m个盘子分苹果
    if n > m:
        return count_ways(m, m)
    # 分为两种情况：至少每个盘子放一个苹果；有盘子空着
    return count_ways(m, n - 1) + count_ways(m - n, n)


t = int(input())  # 测试数据数目
results = []
for _ in range(t):
    m, n = map(int, input().split())
    results.append(count_ways(m, n))
# 输出结果
for res in results:
    print(res)

【陈子良 25物理学院】常规dfs题，按从左到右的顺序遍历盘子，每次选择若干个苹果放进盘子中。为了去重，要求苹果数是单调递减的。

python

for _ in range(int(input())):
    M,N=map(int,input().split())
    s=0
    # n表示当前盘子位置，m表示剩余苹果数，i表示上一个盘子的苹果数
    def dfs(m,n,i):
        if n==N:
            if m<=i:
                global s
                s+=1
            return
        for x in range(min(m,i)+1):
            dfs(m-x,n+1,x)
    dfs(M,1,float('inf'))
    print(s)

M01664: 放苹果 ​

M01664: 放苹果