就是斐波那契数列

#include<bits/stdc++.h>
using namespace std;
const int N = 31;
int dp[N];
int solve1(int n)//递归
{
    if(n <= 3) return n - 1;
    return solve1(n - 1) + solve1(n - 2);
}
int solve2(int n)//记忆化递归（备忘录）
{
    if(dp[n] != 0)
        return dp[n];
    if(n <= 3)
        dp[n] = n - 1;
    else
        dp[n] = solve2(n - 1) + solve2(n - 2);
    return dp[n];
}
int solve3(int n)//动态规划
{
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 2;
    for(int i = 4; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}
int solve4(int n)//动态规划,迭代（空间优化）
{
    if(n <= 3) return n - 1;
    int s1 = 1, s2 = 2;
    for(int i = 4; i <= n; i++)
    {
        // int sum = s1 + s2;
        // s1 = s2;
        // s2 = sum;
        s2 = s1 + s2;
        s1 = s2 - s1;
    }
    return s2;
}
int solve()//动态规划,打表
{
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 2;
    for(int i = 4; i <= N; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
}
int main()
{
    int n;
    solve();
    while(cin >> n)
    {
        //printf("%d\n", dp[n + 1]);//打表
        cout << solve4(n + 1) << endl;
    }
    return 0;
}