六、递归(下)¶
分治策略¶
分治策略¶
递归算法与分治策略¶
优化问题和贪心策略¶
优化问题¶
找零兑换问题¶
贪心策略解决找零兑换问题¶
贪心策略 Greedy Method¶
贪心策略失效¶
找零兑换问题的递归解法¶
找零兑换问题:递归解法¶
找零兑换问题:递归解法代码¶
找零兑换问题:递归解法分析¶
找零兑换问题:递归解法改进¶
找零兑换问题的动态规划解法¶
找零兑换:动态规划解法¶
找零兑换:动态规划算法代码¶
找零兑换:动态规划算法扩展¶
动态规划案例分析¶
讨论:博物馆大盗问题¶
博物馆大盗问题:动态规划表格¶
小结¶
递归小结¶
递归是解决某些具有自相似性的复杂问题的有效技术。
递归算法"三定律"
- 必须具备基本结束条件;
- 必须要减小规模,改变状态,向基本结束条件演进;
- 必须要调用自身。
某些情况下、递归可以代替迭代循环。
递归算法通常能够跟问题的表达自然契合。
递归不总是最合适的算法,有时候递归算法会引发巨量的重复计算。
"记忆化/函数值缓存"可以通过附加存储空间记录中间计算结果,来有效减少重复计算。
如果一个问题最优解包括规模更小相同问题的最优解,就可以和 i用动态规划来解决。