关于DP那些事
__rnfmabj__ · · 算法·理论
DP入门
关于动态规划(DP),有一个简单的小故事
A * "1+1+1+1+1+1+1+1 =？" *
A : "上面等式的值是多少"
B : *计算* "8!"
A *在上面等式的左边写上 "1+" *
A : "此时等式的值为多少"
B : *quickly* "9!"
A : "你怎么这么快就知道答案了"
A : "只要在8的基础上加1就行了"
A : "所以你不用重新计算因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过的解来节省时间'"可以知道动态规划算法的核心是将大问题分解为小问题，记住已经解决过的子问题的解，从而解决主问题
那么我们应该怎样记住主问题呢，有两种方法：
①自顶向下的备忘录法(递归记忆)
②自底向上(递推)
来看一道很水经典的DP题：
斐波那契数列是指这样的数列：数列的第一个和第二个数都为 1，接下来每个数都等于前面 2 个数之和。
给出一个正整数 a，要求斐波那契数列中第 a 个数是多少。这是一个很基础的递推题，甚至递推式都有 : f[ i ]=f[ i-1 ]+f[ i-2 ]
直接上伪代码：
int n,a[31]=[0,1,1],i;//首先定义一个循环变量
cin>>n;// 再定义一个数组记录斐波那契数列的第n项，并且初始化第0项,第1项和第二项。
for (i=3;i<=n;i++){然后一个 for 循环，从第3项开始；
a[i]=a[i-1]+a[i-2]; //利用递推公式逐步计算每一项的值；
}
cout<<a[n]<<endl;当然，这只是最简单的递推，但别忘了我们还有递归
int a[31];//记忆化
void fib(int i){
if(i==1 || i==2) return a[i]=1;//第1项和第2项返回1
if(i==0) return a[i]=0;//第0项返回0
if(a[i]!=0) return a[i];//子问题解决过直接返回
return a[i]=fib(i-1)+fib(i-2);//没有解决过
}好了，你已经学会DP了，快去刷黑题吧
接下来，是另一道很水基础的DP题
楼梯有 N 阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。第一眼看到这题的童鞋可能会被吓到，但实际上只要简单地想一下：
想要上到底 i 个台阶，我们只能从第 i - 1 和第 i - 2 个台阶上来。也就是说，我们只需要求出上到第 i - 1 层和第 i - 2 层台阶的方案总数，就可以出答案，然后就得出了递推式：