[数据结构与算法]NTU 课程笔记：MAS714（9） 动态规划

1  动态规划和分治的区别

        分治：问题分成几个独立的子问题，他们会分别解决。最后再将各个子问题的结果合并成一个大的结果

        动态规划：问题分成几个相互依赖或者重叠的问题。使用空间换时间的方法避免重复计算，一般从下往上计算子问题。

2 动态规划举例：斐波那契数列

2.1 斐波那契额数列的描述

其中F(0)=0，F(1)=1

2.2 斐波那契数列的通项

高中还会求的，好像是解一元二次方程然后算系数（记不清了，之后回家翻一下笔记补上去。。。）

总之，斐波那契数列的通项是：

其中是黄金比例

与此同时，我们有：

开通VIP 解锁文章