算法学习随笔05

[IAn2018cs]

Gmeek-html<img src="https://blog-image.ian2018.cn/images/fd688f3969faa60a5550a3ee0f2f2fd72d42964a.png">

Week06 学习笔记

动态规划

将一个复杂的问题，用一种递归的方式分解成简单的子问题。

动态规划就是分治 + 最优子结构

动态规划与分治对比：

• 动态规划和递归或分治没有根本上的区别（关键看有无最优子结构）
• 共性：找到重复子问题
• 差异性：最优子结构、中途可以淘汰次优解

动态规划关键点：

1. 最优子结构 opt[n] = best_of(opt[n-1], opt[n-2], ...)
2. 存储中间状态：opt[i]
3. 递推公式（状态转移方程或DP方程）
   • 如 斐波拉契数列：opt[i] = opt[n-1] + opt[n-2]