文章来自于公众号，原地址https://mp.weixin.qq.com/s/lBXc_0YXhKxLsrGhNH80Mw
动态规划是一种常用的算法思想，很多朋友觉得不好理解，其实不然，如果掌握了他的核心思想，并且多多练习还是可以掌握的。下面我们由深入浅地来讲讲动态规划。
斐波那契数列
首先我们来看看斐波那契数列，这是一个大家都很熟悉得数列：
// f = [1, 1, 2, 3, 5, 8]
f(1) = 1;
f(2) = 1;
f(n) = f(n-1) + f(n-2)
递归版斐波那契数列
有了上面得公式，我们很容易写出计算f(n)得递归代码：
现在我们考虑一下上面得计算过程，计算f(5)的时候需要f(4)和f(3)的值，而计算f(4)的时候需要f(3)和f(2)的值，这里f(3)就重复算了两遍。在我们已知f(1)和f(2)的情况下，我们其实只需要计算f(3)，f(4)，f(5)三次计算就行了，但是为了计算f(5)，我们总共计算了8次其他的值，里面f(3)，f(2)，f(1)都有重复的多次计算。如果n不是5，而是一个更大的数，计算次数更是指数级增长，这个递归算法的时间复杂度是O(2n)。
带记忆的递归的斐波那契数列
非递归的斐波那契数列
为了解决上面指数级的时间复杂度，我们不能用递归算法了，而要用一个普通的循环。
钢条切割问题
某公司出售钢条，出售价格与钢条的长度之间的关系如下图
| 长度i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 价格pi | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |
| 问题：现有一段长度为n的钢条和上面的价格表，求切割钢条的方案，使得总收益最大。 |
递归方案
以长度为5的钢条为例，假设只切一刀，情况有4种，
- [1, 4]
- [2, 3]
- [3, 2]
- [4, 1]
分成了左右两部分，两部分又分别可以继续切，而每部分一切，又变成了两部分，又可以继续切。
写成公式为：rn = max(pn, r1+rn-1, r2+rn-2, ... , rn-1+r1) - rn: 表示求解的目标
- pn: 表示一刀也不切
- r1 + rn-1: 表示左边为1， 右边为n-1长度的两端。
动态规划
最长公共子序列的长度
一个序列的子序列是在该序列中删除若干元素后得到的序列，如ABCD和BDF都是ABCDEFG的子序列，不考虑连续。
递归方案
动态规划
