动态规划之青蛙跳台阶

–就是斐波那契数列

// 一个青蛙，一次只能跳以及台阶，或者跳两级台阶。

// 问： 这个青蛙跳上 n 级台阶有多少种跳法？

// 如果这只青蛙，跳上了第 n 级台阶，那么最后一次跳跃之前，它一定在 n-1 级台阶 或 n-2 级台阶上。
// 那么跳上 n 级台阶有多少种情况就变成两个子问题
// 跳上 n-1 级台阶的跳法 加上 跳上 n-2 级台阶的跳法

// 按照此逻辑递推，跳上 n-1 级台阶可以拆解为两个子问题
// 即: 跳上 n-2 级台阶的跳法 加上 跳上 n-3 级台阶的跳法

// f(n) = f(n-1) + f(n-2)
// f(n-1) = f(n-2) + f(n-3)
// f(n-2) = f(n-3) + f(n-4)

function jump(n) {
    if (n <= 0) return -1;
    if (n == 1) return 1;
    if (n == 2) return 2;
    return jump(n - 1) + jump(n - 2);
}

console.log(jump(8));