动态规划-变态青蛙跳台阶

变态青蛙跳台阶
一只青蛙，一次只能跳1级台阶、2级台阶、3级台阶、…、n级台阶
问：这只青蛙跳上n级台阶，有多少种跳法

递推公式：
f(n) = f(n -1) + f(n-2) + f(n-3) + … + f(1) + f(0)

实现方法

还是基于斐波那契数列方法

/*** 变态青蛙跳台阶* 一只青蛙，一次只能跳1级台阶、2级台阶、3级台阶、...、n级台阶* 问：这只青蛙跳上n级台阶，有多少种跳法*/// f(n) = f(n -1) + f(n-2) + f(n-3) + ... + f(1) + f(0)function jump(n) {if (n <= 0) return -1if (n === 1) return 1if (n === 2) return 2let result = 0for (let i = 1; i < n; i++) {result += jump(n - i)}return result + 1 // +1表示从0级台阶直接跳上去的情况
}/*** 1 1 1 1* 1 1 2* 1 2 1* 1 3* 2 1 1* 2 2* 3 1* 4*/
console.log(jump(4)) // 8