本题用动态规划求解，题解写的时间上，看的人少，请多多点赞支持

本题是斐波那契数列的一个变种，主要考察的是大数加减法
java中可以使用BigInteger类实现大数加减
c++我是参考 ‘广州市民林先生’的题解，将斐波那契中的两个数转为字符串，然后一位位加，具体实现看代码，注释很详细
python3不用管大数，int类不会溢出，就是普通的斐波那契，惊了

附上斐波那契数列状态转移方程：dp[i] = dp[i-1]+dp[i-2]
这是我之前写的斐波那契数列题解
（最后吐槽一下，这题真的是考察动态规划吗？）

<>alt
显示有问题，将就着看吧

#include <iostream>
#include <string>
using namespace std;

string BigData(string s1, string s2){
    string res = "";
    int i = s1.size() - 1;
    int j = s2.size() - 1;
    int carry = 0;  //进位
    while (i >= 0 || j >= 0){
        // s2一定大于s1（斐波那契数列的后者 > 前者）
        if(i < 0){
            //当小的字符串先走完时，就剩大字符串了，同理进行逐位添加
            res = to_string((s2[j] - '0') + carry) + res;
            carry = 0;  //只剩一个字符串就不存在进位了，因为都是个位数
        } else{
            //从后往前进行逐位相加，如123+567,从3+7开始往前加，别忘了加上进位
            int tmp = (s1[i] - '0') + (s2[j] - '0') + carry;
            carry = tmp / 10;  //得到进位
            tmp = tmp % 10;    //得到余数
            res = to_string(tmp) + res; //这里顺序记得不能颠倒，不然就错了
        }
        --i; --j;
    }
    //为什么下面还要判定呢？因为比如3+7应该等于10，但是
    //上面的计算出的res只有0(余数)，所以这里要考虑周全
    if(carry == 1)
        res = '1' + res;
    return res;
}
int main(){
    int n;
    cin >> n;
    //斐波那契
    if(n == 1){
        cout << 1 << endl;
        return 0;
    } else if(n == 2){
        cout << 2 << endl;
        return 0;
    }
    string i = "1";
    string j = "2";
    string ans = "";
    for(int k = 1; k <= n - 2; ++k){
        ans = BigData(i, j);  // i + j
        i = j;   
        j = ans;
    }
    cout << ans << endl;
    return 0;
}

import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws Exception {
        StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(
                    new InputStreamReader(System.in)));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        int length ;
        streamTokenizer.nextToken();
        length = (int) streamTokenizer.nval;
        if (length < 3) {
            pw.println(length);
            pw.flush();
            return;
        }

        /*BigInteger[] dp = new BigInteger[length+1];
        dp[1] = BigInteger.ONE;
        dp[2] = BigInteger.valueOf(2);
        for (int i = 3; i <= length; i++) {
            dp[i] = dp[i-1].add(dp[i-2]);
        }*/

        BigInteger dpi = BigInteger.ZERO;
        BigInteger dpi_1 = BigInteger.ONE;
        BigInteger dpi_2 = BigInteger.valueOf(2);
        for (int i = 3; i <= length ; i++) {
            dpi = dpi_1.add(dpi_2);
            dpi_1 = dpi_2;
            dpi_2 = dpi;
        }

        pw.println(dpi);
        pw.flush();
    }
}

import sys

length = int(input())

dpi_1, dpi_2 = 0, 1
temp = 0
for i in range(length):
    temp = dpi_1+dpi_2
    dpi_1 = dpi_2
    dpi_2 = temp

print(temp)