记忆化搜索

[Ir1d]

https://oi-wiki.org/dp/memo/

[yltx]

orz，看懂了，写的挺好

[Lutra-Fs]

白书《挑战程序设计竞赛》里就是通过记忆化搜索引出的数组DP

[yxd0379]

请问除了数组dp还有用别的数据结构的dp吗？（好奇

[xxiThubmsk]

chatgpt:

是的，除了数组，动态规划也可以基于其他数据结构进行求解，比如图论中的 DAG（有向无环图）和树形结构。

DAG 动态规划
如果问题中存在一个 DAG，那么可以使用 DAG 上的动态规划求解。将 DAG 拓扑排序得到的序列作为状态的考虑顺序，由前面的状态转移得到后面的状态，从而求出问题的最终结果。

状态压缩动态规划
状态压缩动态规划主要用于求解状态空间较大的问题。在状态空间很大的情况下，使用数组记录所有状态会占用较大的空间，因此可以使用二进制位来表示一些状态，将状态压缩存储，从而节约内存空间。

树形DP
树形 DP 主要用于求解树形结构中的动态规划问题。在树形 DP 中，要对每个节点的子树进行遍历，求解以每个节点为根的子树的最优解，最后统计得到整棵树的最优解。

这些方法都是动态规划在不同领域的扩展和应用，通过选择不同的数据结构，可以更好地解决不同类型的问题。

[Acfboy]

这篇写得比其它的一些好多了！

[ghost]

写得真好，谢谢

[zmxqs]

$qaq++$，非常详细的解析，让萌新一听就懂（虽然我早就会了），这为后面dp的铺垫很好 啊！

[14w10]

@ZhangBo1191
白书《挑战程序设计竞赛》里就是通过记忆化搜索引出的数组DP

数组DP？

[zouyishan]

写的很好 赞赞赞

[zhangxj19]

整挺好

[xy-fs]

感谢！非常的通俗易懂👍

[10000point]

非常通俗易懂，谢谢！

[Nback1]

dfs(pos,tleft)的返回值应该是在tleft时间内，后 n+1 - pos 个草药，能获得的最大收益的

[big5s]

讲得太好了，一听就懂

[lewis666a]

$orz$，讲得好！

[niubidejuruo]

建议添加一些练习题

[Lane0218]

感谢 写得好好！
在洛谷找到了应该是作者的原文，这个更详细一点，可以结合着一起看
https://www.luogu.com.cn/article/qay8mori

[mahaoming2022]

写的很好

[zzzezhang]

请教下 方法二里的 “无需外部变量” 这个是指什么