用 dp[i] 表示走到第 i 个台阶数的方案数

第 i 级台阶可以由第 i-1 和第 i-2 级台阶上来

所以递推公式 dp[i]=dp[i-1]+dp[i-2]

递推初始值为 dp[1]=1,dp[2]=2

#include<bits/stdc++.h>
using namespace std;
#define ioio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define debug(x) cout<<#x<<":"<<x<<endl;
#define L(k) k<<1
#define R(k) k<<1|1
#define P pair
#define P1 first
#define P2 second
#define u_map unordered_map
#define p_queue priority_queue
typedef long ll;
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int INF2 = (1 << 31);
const int N = 1e6 + 7;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
/*-------------------------------------------------*/

int n;
ll dp[N];

int main() {
	ioio
	dp[1]=1,dp[2]=2;
	for(int i=3;i<=75;i++)
		dp[i]=dp[i-1]+dp[i-2];
	cin>>n;
	cout<<dp[n]<<endl;
	return 0;
}

#include<stdio.h> //动态规划 第n个台阶可能是从n-1上来的也可能是从n-2上来的 //f(n)=f(n-1)+f(n-2) long f[71]; long Climb(int n){ f[0] = f[1] = 1; for(int i=2; i<=n; i++){ f[i] = f[i-1] + f[i-2]; } return f[n]; } int main(){ int n; scanf("%d",&n); printf("%ld\n",Climb(n)); }

这题和Fibonacci数列比较相似，本质上是一个简单的动态规划。 递推公式为：dp[i] = dp[i-1] +dp[i-2] 注意dp数组的初始化，dp[1]=1,dp[2]=2。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL dp[100];

int main(){
// dp[n] = dp[n-1] + dp[n-2]
// dp[0] = ? dp[1] = 1 dp[2] = 2
int n;
cin>>n;
dp[1]=1;dp[2]=2;
for(int i=3;i<=n;i++){
dp[i] = dp[i-1]+dp[i-2];
}
cout<<dp[n];
return 0;

}

#include<bits/stdc++.h>
using namespace std;
long long a[1000000]={1,2};
int main(){
	long long n;
	cin>>n;
	for(int i=2;i<n;i++){
		a[i]=a[i-1]+a[i-2];
	}
	printf("%lld",a[n-1]);
	return 0;
}

不开long long 见祖宗,该题可能接近70的时候会越界

#include<iostream>
#include<cmath>
using namespace std;
using ll = long long;
const int N = 75;
ll f[N];
int main()
{
    int n;cin>>n;
    f[1] = 1;
    f[2] = 2;
    for(int i = 3;i <= n;i++)
    {
        f[i] = f[i-1] + f[i-2];
    }
    cout<<f[n]<<"\n";
    return 0; 
}

一道简单的动态规划问题，设到第i节台阶的方案数为dp[i]，则dp[i] = dp[i-1] + dp[i-2]；

#include<bits/stdc++.h>
using namespace std;

long long n,dp[75];

int main(){
	cin>>n;
	dp[0] = dp[1] = 1;
	for(int i = 2;i<=n;i++){
		dp[i] = dp[i-1]+dp[i-2];
	}
	cout<<dp[n];
	return 0;
}

#include <stdio.h>
int main(){
	unsigned long long f1,f2,f,n=0;
	scanf("%lld",&n);
	n=n+1;
  	f1=1;
  	f2=1; 
  	if(n<=2){
  		f=1;
	  }else{
	  	for(int i=3;i<=n;i++){
  		f=f1+f2;
  		f2=f1;
  		f1=f;
	  }
	  }
	printf("%lld",f);
  	return 0;
}