题解 | #跳台阶扩展问题#
跳台阶扩展问题
https://www.nowcoder.com/practice/953b74ca5c4d44bb91f39ac4ddea0fee?tpId=230&tqId=2361300&ru=%2Fpractice%2Fbfb2a2b3cdbd4bd6bba0d4dca69aa3f0&qru=%2Fta%2Fdynamic-programming%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D230
#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)
