动态规划的正确打开
动态规划的正确打开
跳台阶
题目描述：
一个楼梯共有n级台阶，每次可以走一级或者两级，问从第0级台阶到第n级台阶一共有多少种方案。
输入格式：
共一行，包含一个整数n。
输出格式：
共一行，包含一个整数，表示方案数。
数据范围：
1≤n≤15
输入样例：
5
输出样例：
8
dfs的code：
#include<iostream>
using namespace std;
int n;
int dfs(int x){if(x==1) return 1;if(x==2) return 2;else return dfs(x-1)+dfs(x-2);
}
int main(){cin>>n;int res=dfs(n);cout<<res<<endl;return 0;
}
记忆化搜索的code：
#include<iostream>
using namespace std;
int n;
int mem[100];
int dfs(int x){if(mem[x]) return mem[x];int sum=0;if(x==1) sum=1;else if(x==2) sum=2;else sum=dfs(x-1)+dfs(x-2);mem[x]=sum;return sum;
}
int main(){cin>>n;int res=dfs(n);cout<<res<<endl;return 0;
}
递推的code：
#include <iostream>
using namespace std;
int main(){int n;int f[20];cin>>n;f[0]=1;for(int i=1;i<=n;i++){f[i]=f[i-1]+f[i-2];}cout<<f[n-1];return 0;
}