​ 本文从Fibonacci数列的求解来简单介绍动态规划的基本思想与一般解法。

从Fibonacci数列讲起

​ Fibonacci数列在各种科目的教材中出现的次数很多，多为引出递归这一思想的样例，大家都比较熟悉，而此处，我用这一例子来阐述动态规划的基本思想、方法。

我们已知Fibonacci数列性质如下：

$$F(0)=0, F(1)=1 \\ F(i)=F(i-1)+F(i-2)\ \ \ \ i=2,3,4,...,n$$

一般的递归解法如下：

int F(int n)
{
    if(n<0)		return -1;//假设非法输入返回-1
	if(n==0)	return 0;
    if(n==1)	return 1;
    return F(n-1)+F(n-2);
}

​ 但是递归的方法显然会出现重复计算（比如计算$F(3)=F(2)+F(1)=(F(1)+F(0))+F(1)$ ,当n更大时，重复计算更多)，时间复杂度为$O((\frac{1+\sqrt{5}}{2})^n)$（时间复杂度的详细计算可以自行搜索），明显不是一个好的算法。

动态规划——递归+重复值的记录

​ 很明显，改进递归算法的方向之一是减少重复计算，如何解决？我们用数组的形式记录之前已经计算过的值。

​ 通过简单的改进，具有简单递归思想的算法如下：

int F(int n)
{
    if(n<0) return -1;//假设非法输入返回-1
    vector<int> fib(n+1,0);
    fib[1]=1;
    for(int i=2;i<=n;i++){
        fib[i]=fib[i-1]+fib[i-2];
    }
    return fib[n];
}

​ 用fib数组来储存之前计算过的斐波那契数，不用再递归求解。由于循环中$i$由小到大，所以我们能够保证在求解$fib[i]$时，$fib[i-1], fib[i-2]$已经被求解出来。

动态规划思想简括

​ 所以动态规划的思想可以简单地概括为：

$$DP=recursion+memorization$$

• recursion: 问题本质可以数学化为递归数列的求解，能找到相应的递推公式

• memorization: 通过数组或其他变量来存储已经计算过的项，减少重复计算

所以在

1.对问题最有解法可用于子问题（recursion）。

2.子问题与原问题有相交（overlap），且递归的解包含子问题的解且重复多次（可用memorization）。

两者同时成立时，可以考虑用DP解决该问题。

如果理解的话，尝试一下自己能否独立写出$leetcode$上这道$Fibonacci$数列的题呢？

509-斐波那契数