DP入门系列-DP入门指导

DP入门指导

最近在入门dp，当然我还不会dp。不过我已经放下了狠话，我学不会dp我退出实验室。。。
先解释一下DP的最入门的概念：
用我师傅传授给我的一句话说，DP是什么呢，核心是避免重复计算。举个栗子吧。
如果你想算斐波那契额数列的话很简单，但是如果算的数值太大了，比如说，你算到第50位，那么应该怎么算呢？？？OK咱们先按照正常的思路来写一下正常的斐波那契数列。

#include<stdio.h>
typedef long long ll;
ll F(int a)
{if(a==1||a==2)
return 1;
return F(a-1)+F(a-2);
}
int main()
{
 int num;
 scanf("%d",&num);
 printf("%lld\n",F(num));
 return 0;
 } 

OK，我想这应该是一个非常好理解的斐波那契数列，那么咱们测试一下这个程序的性能。

好我们可以看到，跑50就用了接近1分钟，那么你这个程序放在服务器上测评绝对是要出问题的啊。所以说这个是一个大的毛病。分析一下原因。为什么会出现这样的情况。

我们可以想一下，每一次计算是不是都要依据你的前一项和你的前两项。这样的话你的前一项是不是又得依赖你的前一项和前俩项。但是算出来的结果是不是可以给别的用？比如说你想算F(5)那么你得算出F(4)和F(3)而F(4)又得算出F(3)和F(2))按理说你已经把F(3)算出来了，可是，F(3)还是要再执行一次那些没有意义的操作。所以这就重复计算了。那么怎么用DP解决这个问题呢？？

结果很显然，包括输入时间在内一共用了不到一秒钟。
改进后的DP代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[5000];
ll F(int a) {
 if(dp[a]!=-1)
  return dp[a];
 ll temp=F(a-1)+F(a-2);
 dp[a]=temp;
 return temp;
}
int main() {
 memset(dp,-1,sizeof(dp));
 dp[1]=dp[2]=1;
 int num;
 cin>>num;
 cout<<F(num)<<endl;
 return 0;
}

如此操作的话我们把算过的每一个斐波那契数列都存储了一下，这样的话我们就可以需要的时候直接调用，就剩去了那些繁琐的重复计算。

所以说DP最重要的就是状态转移，换句话说就是当你可以调用的时候就不用再去求一次了。比如说，让你算1+1+1+1+1等于几。很明显答案等于5，那么如果让你算1+1+1+1+1+1呢？你是选择算6次还是说选择在之前5次的基础的状态之上转移过来直接运算？肯定是后者，那么答案直接出来5+1=6。

这样DP的序章终于可以拉开帷幕了！！！
By-轮月