小议动态规划x
来源：高三 发布时间：2020-08-28 点击：
小议动态规划 从分治到动态规划，中间隔了重叠子问题（overlapping subproblems）
• 记忆化体（memo）存放的是子问题（subproblems）的 solution
stored subproblem solutions • 动态规划仍然是一种暴力算法 brute force（也即遍历所有的可能性），只是 memo 的存在避免了重复计算； 0. 动态规划其名 “动态规划”（dynamic programming）一词源于研究优化问题的数学理论，这一名称其实与计算机领域中常用的“动态”（dynamic）和“编程（programming）”没有任何关系。动态规划的发明者贝尔曼称， dynamic：是因为单词本身的魅力，而不关于其内在含义； • programming 在研究优化的领域中表示“ 搜索最优程序”的意思； 所以，不要从字面上去理解动态规划，而是从其具体的操作上。
1. 动态规划与分治