好像就是一个找规律
当n = 1 时 只有一种可能 ：0 -> 1
当n = 2 时 有两种可能：0 -> 1 -> 2 0 -> 2
当n = 3时 三种可能：0 -> 1 -> 2 -> 3 0 -> 2 -> 3 0 -> 1 -> 3
当n = 4时 五中可能：0 -> 1 -> 2 -> 3 -> 4 0 -> 2 -> 3 -> 4 0 -> 1 -> 3 -> 4 0 -> 1 -> 2 -> 4 0 -> 2 -> 4
到此自信的小朋友已经断定是个斐波那契了
原因大概就是当n = 4的时候 是在n = 3的所有结果上再跳一格到4 加上 n = 2的所有结果挑两个到4

C++ 代码

#include <iostream>

using namespace std;

const int N = 20;
int 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] << endl;

    return 0;
}