AcWing 821. 跳台阶
原题链接
困难
作者:
咸鱼堆上的猫
,
2024-04-10 19:39:24
,
所有人可见
,
阅读 1
//递归写法
#include<bits/stdc++.h>
using namespace std;
int n;
int dfs(int x)
{
if(x==1) return 1;
if(x==2) return 2;
else return dfs(x-2)+dfs(x-1);
}
int main()
{
cin>>n;
cout<<dfs(n);
}
//记忆化递归 m[x]存储已经计算的台阶方案 避免重复计算
#include<bits/stdc++.h>
using namespace std;
int n,k;
int m[15],sum;
int dfs(int x)
{
if(m[x]) return m[x];
if(x==1) return 1;
if(x==2) return 2;
else{
sum = dfs(x-2)+dfs(x-1);
}
m[x]==sum;
return sum;
}
int main()
{
cin>>n;
cout<<dfs(n);
}
dp法 就是递归回溯的过程
#include<bits/stdc++.h>
using namespace std;
int n,k;
int dp[16];
int main()
{
cin>>n;
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++) dp[i]=dp[i-2]+dp[i-1];//从递归树的最下往上,最下面就是边界 递归出口
cout<<dp[n];
}