青蛙跳台阶

划分子问题:
一层：1
二层：11 2
三层：111 12
四层：1111 112 22
五层：11111 1112 122 ......
仔细想一想：
从三层楼开始：
不管是有几层楼梯，都是要选择先跳一层还是先跳两层

假如我先跳一层，子问题就变成了f(n-1)个跳法的问题，
假如我先跳两层，子问题就成了f(n-2)个跳法的问题。
往下层子模块叠加

所以，这和斐波那契数列问题一样：

递归解法

#include<iostream>
using namespace std;

int jump(int n){
    if( n == 0 )
        return 0;
    else if( n == 1 )
        return 1;
    else if( n == 2 )
        return 2;
    else
        return jump(n-1)+jump(n-2);
}

int main(){
    int num;
    cin >> num;
    cout << jump(num) <<endl;
    return 0;
    
}

动态规划

#include<iostream>
using namespace std;

int jump(int n){
	int j[n];
    if( n == 0 )
        return 0;
    else if( n == 1 )
        return 1;
    else if( n == 2 )
        return 2;
    else
        j[n]=jump(n-1)+jump(n-2);
    return j[n];
}

int main(){
    int num;
    cin >> num;
    cout << jump(num) <<endl;
    return 0;
    
}