思路：**还是feibonacci问题。
#include<iostream>
#include <vector>
using namespace std;

int main()
{
    vector<long long> v(91);
    v[1] = 1;
    v[2] = 2;
    for (int i = 3; i < 91; i++)
    {
        v[i] = v[i - 1] + v[i - 2];
    }
    int n;
    while (cin >> n)
    {
        cout << v[n] << endl;
    }
}

详细解释
https://blog.csdn.net/qq_33375598/article/details/104605811
以下为上述博文中的内容，谢谢支持！

当n为1和2时，情况分别是1，2，当n为3时，就是在前面的基础上增加，如下图所示。

当n为4时，就是下面这种情况：

依次递推。不过本质就是斐波那契数列问题，初值为F（1）= 1，F(2) = 2，公式为F(n) = F(n -1)+F(n-2)。

下面时斐波那契问题的求解：

• 记录子问题的解，来避免下次遇到相同子问题时的重复计算。
  以斐波那契数列为例子：
  斐波那契数列定义为F0 =1,F1 = 1,Fn = Fn-1+Fn-2(n>=2)
  递归写法为：

int F(int n){
    if(n == 0 || n == 1) return 1;
    else return F(n-1) + F(n-2);
}

这个递归会涉及到很多重复的计算,如当n==5时，可以得到F(5)= F(4)+F(3),接下来计算F(4)时又会有F(4)= F(3)+F(2),这时不采取措施，F(3)将会被计算两次。如果n很大，重复计算的次数将难以想象。

实际上由于没有保存中间计算的结果，实际复杂度将会高达O(2^n^),即每次都会计算F(n-1)和F(n-2)这两个分支，基本上不能承受n较大的情况。

开一个数组dp,用来保存已经计算过的结果，其中dp[n]记录F(n)的结果，并用dp[n] = -1来表示F(n) 当前还没有被计算过。

int dp[MAXN];

然后就可以在递归中判断dp[n]是否是-1，如果不是-1，说明已经计算过F(n),直接返回dp[n]就是结果；否则，按照递归式进行递归。

int F(int n){
    if(n == 0 || n == 1) return  1;
    if(dp[n] != -1) return dp[n];
    else{
        dp[n] = F(n-1) + F(n-2);
        return dp[n];
    }
}

通过记忆化搜素，把复杂度从O(2^n^)降到O(n)。
斐波那契数列递归图：

斐波那契数列记忆化搜索示意图：

如计算F（45），直接使用递归用时9.082809，用记忆化搜索仅仅0.000001

3 参考代码

//https://blog.csdn.net/qq_33375598/article/details/104605811
#include <cstdio>
(802)#include <cstring>

typedef long long ll;
const int MAXN = 10000;
ll dp[MAXN];
ll F(int n){//动态规划的递推写法
    if(n == 1) return 1;
    if(n == 2) return 2;
    if(dp[n] != -1)  return dp[n];//记忆化搜素
    else{
        dp[n] = F(n - 1) + F(n - 2);
        return dp[n];
    }
}

int main(int argc, char const *argv[]){
    int n;
    while(scanf("%d", &n) != EOF){
        memset(dp, -1, sizeof(dp));
        printf("%lld\n", F(n));
    }
    return 0;
}

python solutoin

仔细思考，就会发现这本质上是跳台阶的问题。也就是一个Fibonacci数列

import sys


def programsNumber(n):
    arr = [1, 2]
    while len(arr) < n:
        arr.append(arr[-1] + arr[-2])
    return arr[n - 1]


for i in sys.stdin.readlines():
    print(programsNumber(int(i)))

#include<cstdio>
using namespace std;
long ans[91];
int n;
int main(){
	ans[1]=1;
	ans[2]=2;
	for(int i=3 ;i<=90 ;i++){
		ans[i] = ans[i-1] + ans[i-2];
	}
	while(scanf("%d",&n)!=EOF){
		printf("%ld\n",ans[n]);	
	}
	return 0;
} 

#include <iostream>
 
using namespace std;
 
int main() {
     
    unsigned long n;
    while(cin >> n){
     unsigned long f = 0, g = 1;
    while (0 < n--) {
        g += f;
        f = g - f;
    }
    cout << g << endl;
    }
    return 0;
}

放第n的时候,可在n-2的情况下在最右边横着放两块,有a[n-2]种情况,也可在n-1的情况下在最右边竖着放一块,有a[n-1]种情况.

故:a[n]=a[n-2]+a[n-1]

def sq(n):
    res = [1,2]
    while len(res)<n:
        res.append(res[-1]+res[-2])
    return res[n-1]

while True:
    try:
        inputs = int(input())
        print(sq(inputs))
    except:break

#include<stdio.h>
long fib(int n)
{
    long pre = 1;
    long next = 0;
    long result = 1;
    while(n > 1)
    {
        n--;
        next = pre;
        pre = result;
        result = next + pre;
    }
    return result;
}
int main(void)
{
    int n;
    while(scanf("%d", &n) != EOF)
    {
        printf("%ld\n", fib(n));
    }
}

	#include <stdio.h>



	voidDataInit(longlong*a);



	intmain()



	{



	    intN, i;



	    longlongA[100001] = {0, 1, 2};



	    DataInit(A);



	    while(scanf("%d", &N)!=EOF)



	    {



	        printf("%lld\n", A[N]);



	    }



	      



	    return0;



	}



	voidDataInit(longlong*a)



	{



	    inti;



	    for(i=3;i<100001;i++)



	    {



	        a[i] = a[i-1] + a[i-2];



	    }



	}

 public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        while (s.hasNext()) {
            int x = s.nextInt();
            long a[] = new long[x + 2];
            a[1] = 1;
            a[2] = 2;
            if (x > 2) {
                for (int i = 3; i <= x; i++) {
                    a[i] = a[i - 1] + a[i - 2];
                }
            }
            System.out.println(a[x]);
        }
    }

import java.util.Scanner;
public class Main {
private static long[] a = new long[91];
        private static int min = 4;
        static {
            a[1]=1;a[2]=2;a[3]=3;a[4]=5;
        }
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            while (in.hasNextInt()) {//
                int n = in.nextInt();
                System.out.println(cal(n));
            }
            in.close();
        }
        private static long cal(int n) {
            if(min < n) {
                int i = min;
                while(++i <= n) {
                    a[i] = a[i - 2] + a[i - 1];
                }
            }
            return a[n];
    }
}

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int main(){

long long a[91];
a[1]=1;a[2]=2;
a[3]=3;a[4]=5;

int min=4;
int n;

while((scanf("%d",&n))!=EOF){
	if(n>min){
		for(int i=min+1;i<=n;i++){//根据需求动态计算所需结果，并且随着程序运行时间越来越差，
								//数据库会越发完善 
	a[i]=a[i-1]+a[i-2];
}
	}
	printf("%lld\n",a[n]);
} 








return 0;
}

#include <stdio.h>
int main()
{
    long long arr[91];
    int i,n;
    arr[1]=1;
    arr[2]=2;
    for(i=3;i<=90;i++)
        arr[i]=arr[i-1]+arr[i-2];
    while(scanf("%d",&n)!=EOF){
        printf("%ld\n",arr[n]);
    }
    return 0;
}