动态规划概念：

给定一个问题，将其拆成一个个子问题，直到子问题可以直接解决。然后把子问题的答案保存起来，以减少重复计算。再根据子问题的答案反推，得出原问题解。

821

运行时间长的原因：

重复大量计算

以5个台阶为例：

 正确做法：记录台阶已有的方案，比如用mem[]数组记录

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=30;
int n;
string words[N];//存单词
int used[N];//记录每个单词的使用次数
int g[N][N];//f[i][j] 存第i个单词能否接到第j个单词后面,存储相同子串长度
int res=0;
int mem[N];
int dfs(int x)//x代表遍历到的单词
{

if(mem[x])return mem[x];//如果以计算好直接返回
int sum=0;
if(x==1)
sum=1;
else if(x==2)//用else if
sum=2;
else sum=dfs(x-1)+dfs(x-2);
mem[x]=sum;//没有计算好则需要更新
return sum;
}
int main()
{
scanf("%d",&n);
int res=dfs(n);
printf("%d\n",res);
return 0;
}

递推算法dp：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=30;
int n;
int res=0;
int mem[N];
int main()
{
scanf("%d",&n);
mem[1]=1;
mem[2]=2;
if(n==1||n==2)
printf("%d",mem[n]);
for(int i=3;i<=n;i++)
{
mem[i]=mem[i-1]+mem[i-2];
}
printf("%d\n",mem[n]);
return 0;
}

进一步优化空间：

int newf=0,tmp1=1,tmp=2;

for(int i=3;i<=n;i++)

{

newf=tmp1+tmp2;

tmp1=tmp2;

tmp2=newf;} 

 记忆化搜索=暴力dfs+记录答案

递推的公式=dfs向下递归的公式

递推数组的初始值=递归的边界

acw1049