题解 | #跳台阶扩展问题#

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    
    int n;
    scanf("%d", &n);
    int  dp[21] = {0};
    dp[0] = 1;
    dp[1] = 1;
    //dp[i]满足公比为2的 等比数列
    printf("%d",(int)pow(2,n-1));
    return 0;
}
// 64 位输出请用 printf("%lld")

找规律：

dp[0] = 1

dp[1] = dp[0] = 1

dp[2] = dp[0]+dp[1] = 2 : 从0走2步+从1走1步

dp[3] = dp[0]+dp[1]+dp[2] = 4

dp[n] = 2^n-1