动态规划学习笔记

动态规划

斐波那契数列

斐波那契数列中的每一个数字都是这个数字前两个数字的和。

Fibonaccci Sequence
1	1	2	3	5	8	13	21

而如果用一个公式来表示数列中的任意一个数则是(n>1)：
$$fib(n)=fib(n-1)+fib(n-2)$$
用代码表示：

long long fib(long long n){    //求斐波那契数列中第n个数
    if(n==1||n==2){  
        return n;  
    }
    return fib(n-1)+fib(n-2);  //继续递归
}

然而当n较大时，计算量也就极其庞大，而当我们分解计算机的每次计算时会发现有许多重复计算，而计算越庞大，重复计算也就越多，这时我们就得使用一种方法：动态规划。

动态规划

动态规划是对解最优化问题一种设计方法或思想，并不能算是算法，而这个方法中包含多种算法，如递归，分解等。动态规划通过把原问题分解为多个子问题来解决较为复杂的问题。

一型三征

有许多人对动态规划这种优化方案理解的非常透彻并做出了总结，我将其总结为**“一型三征”**。

"一型”指适合问题的最优解模型。

“三征”指的是最优子结构、对后无效性和记忆化搜索。

优化方案

先模拟一个情景：老师布置了100道很复杂的题，但是这100道题都一模一样，那么我们只需计算一道题的结果，再把它抄到其他题上就行了(当然你也可以一个一个算，但真一个一个算的人一定是个傻—），而不幸的是，计算机就是一个这样的傻—，这时我们就可以使用记忆化搜索，就是把每一次的计算结果记录下来，在之后的计算中如果需要某一次的计算结果，直接调用就可以了。

//使用动态规划解决斐波那契数列
long long fib(long long n,long long* memo) {
	if (n == 1 || n == 2) return 1;
	if (memo[n] != 0) return memo[n];
	
	memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
	return memo[n];
}

总结：

动态规划的重点：

1.分解，把原问题分解为多个子问题。

2.一型三征，对问题做出最优解模型，而在某个阶段一旦确定，就不受之后阶段的影响和记忆化搜索。

​ 。。。这里有结尾，这里有结尾。。。