【动态规划.2】5292. 跳台阶

承接上一篇

升级版，别怕，上一篇弄会了，这个就是 豆芽菜✌️
https://www.acwing.com/problem/content/description/5295/
在这里插入图片描述

f1.递归

#include <bits/stdc++.h>  
//  2024-03-08  Come on !
using namespace std;  
#define  ll long long  
ll N;
int  solve(int n){
	if(n==1||n==0)  return 1;
	else if(n==2)  return 2;
	else return solve(n-3)+solve(n-2)+solve(n-1);
	//cout << "Hello world !" << '\n';
	
	
}	
int main() {  
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // no endll;  
	
	int t=1;
	while(t--){
		cin>>N;
		 cout<< solve(N);
	}
	return 0;  
}

f2.记忆化

#include <bits/stdc++.h>  
//  2024-03-08  Come on !
using namespace std;  
#define  ll long long  
ll N,sum;
ll pre_res[100001];
int  solve(int n){
	if(n==1||n==0)  return 1;
	else if(n==2)  return 2;
	else if(pre_res[n]!=0){
	      return pre_res[n];
	        }
    else  {
	   sum=solve(n-3)+solve(n-2)+solve(n-1);
   }  pre_res[n]=sum;
	return sum;
	//cout << "Hello world !" << '\n';
	
}	
int main() {  
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // no endll;  
	
	int t=1;
	while(t--){
		cin>>N;
		 cout<< solve(N);
	}
	return 0;  
}