Poweroj：2425-跳台阶（经典递推）

题目链接：https://www.oj.swust.edu.cn/problem/show/2425

跳台阶

Edit Manage Data Rejudge

Time Limit: 1000 MS Memory Limit: 65536 KB

Total Submit: 380 Accepted: 133 Page View: 1154

Submit Status Discuss

Description

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

Input

输入包含多个测试样例，对于每个测试案例，输入包括一个整数n (1 <= n <= 50)。

Output

对应每个测试案例，输出该青蛙跳上一个n级的台阶总共有多少种跳法。

Sample Input

Sample Output

解题心得：

其实就是一个递推的题，每个如果一个青蛙要跳到第ｎ级台阶，那么这个青蛙可以从它前面的所有的台阶跳到第ｎ级，这样到达第ｎ级台阶的方法就等于前面所有的相加，当然也可以直接跳到第ｎ级，所以最后需要加１，如果想不通可以假设这个青蛙每次只能跳１阶或者跳２阶，这就成了一个斐波那契数列。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 50;

ll method[maxn];

void init() {

    method[1] = 1;

    method[2] = 2;

    for(int i=3;i<=50;i++) {

        for(int j=1;j<i;j++) {

            method[i] += method[j];

        }

        method[i] += 1;

    }

}

int main() {

    init();

    int n;

    while(scanf("%d",&n) != EOF ) {

        printf("%lld\n",method[n]);

    }

    return 0;

}