放苹果

日期：2025-06-10
所用时间：5min

1. 暴力搜索

思路:

使用记忆化搜索解决这个问题。定义状态表示将个苹果放入个盘子中的方案数，其中记录当前每个盘子的苹果数量。
状态转移分析:如果且，说明还有苹果但盘子用完了，返回 0如果，说明所有盘子都分配完了，检查当前方案是否重复对于每个盘子，可以放入 0 到个苹果，递归计算所有可能的方案
去重处理:使用字典记录已经出现过的方案将每个方案排序后转换为字符串作为键值，确保相同方案只计算一次
具体转移方程:当时：检查方案是否重复，返回 1 或 0否则：

时间复杂度: $O(n \times m \times j)$
空间复杂度: $O(n \times m \times j)$

Python3

m, n = map(int, input().split())

vis = {}
def dfs(i, j, path):
    # j 个水果放入 i 个盘子里
    if j > 0 and i == 0:
        return 0
    if i == 0:
        path.sort()
        path = "".join(path)
        if path in vis:
            return 0
        vis[path] = True
        return 1
     
    res = 0
    for cnt in range(j + 1):
        res += dfs(i - 1, j - cnt, path + [str(cnt)])
    return res

print(dfs(n, m, []))

题解 | 放苹果

放苹果

1. 暴力搜索