动态规划 – rooobeam

动态规划

记忆化搜索，递推

入门 DP

理解递推的初始化
问：这个代码和完全背包（例如 518. 零钱兑换 II）的代码很像，二者区别在哪？
答：本题计算的是排列，完全背包计算的是组合。比如 1,2 和 2,1 这两个排列，在本题是有区别的，是两种方案；但在完全背包中这两个排列没有区别，只算一种方案。从代码上看，计算排列（本题）需要外层循环枚举体积，内层循环枚举物品；计算组合（完全背包）需要外层循环枚举物品，内层循环枚举体积。(作者：灵茶山艾府)

数字大时，提前取，加快速度并减小空间。

1
2
3
4
# 提前取模，不然结果会是天文数字，没有那么多空间存得下来
return (dfs(i - zero) + dfs(i - one)) % MOD
# or
f[i] = (fun(i,zero)+fun(i,one)) % MOD

匿名函数，减少冗余代码和加速

1
fun = lambda x,y: f[x-y] if x>=y else 0

标准库 itertools 的 groupby

1
2
3
4
5
6
for ch, s in groupby(pressedKeys):
	print(ch, ''.join(s))
# pressedKeys = "22233"
# 标准输出
# 2 222
# 3 33

最后更新于 2025-09-02