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

#include <stdio.h>

int main() {
    int n,f[21];
    f[1] = 1;
    scanf("%d",&n);
    if(n == 1){
        printf("1");
        return 0;
    }
    for(int i=2; i<=n; i++){
        f[i] = 2*f[i-1];
    }
    printf("%d",f[n]);
    return 0;
}

数学公式推导：

f(n)=f(n-1)+f(n-2)+……+f(2)+f(1) …… ①

f(n-1)=f(n-2)+……+f(2)+f(1) ……②

由①-②得，

f(n) - f(n-1) = f(n-1)

移项得，

f(n) = 2*f(n-1)