法一:DP
#include<iostream>
using namespace std;
int main(){
int dp[16] = {0};//记录中间状态
//dp[i]表示到第n级台阶的方案数
dp[1] = 1;
dp[2] = 2;
int n;
cin>>n;
//已知小问题,能否转移得到大问题
//避免计算重复情况
for(int i = 3;i <= n;i++){
dp[i] = dp[i-1] + dp[i-2];
}
cout<<dp[n]<<endl;
return 0;
}
法二:递归枚举
#include<iostream>
using namespace std;
int res = 0;
int n;
//从i开始
void fun(int i){
if(i >= n){
if(i == n) res++;
return;
}
fun(i + 1);//走一级
fun(i + 2);//走两级
}
int main(){
cin>>n;
fun(0);
cout<<res<<endl;
return 0;
}
法三:王道机试,分治法
#include<iostream>
using namespace std;
//f(n):从0走到n的方案数
//将f(n)分解成若干小问题,直到最小问题f(1)和f(2)可以直接解决
int f(int n){
//递归出口:最小问题解决方案
if(n == 1){
return 1;
} else if(n == 2) {
return 2;//从0走到2有两种方案
} else {//从0走到n的方案数即f(n-1) + f(n-2),因为最后一步要么是0要么是1
return f(n - 1) + f(n - 2);
}
}
int main(){
int n;
cin>>n;
cout<<f(n)<<endl;
return 0;
}