【前端】自学基础算法 -- 23.动态规划-青蛙跳台阶
动态规划-青蛙跳台阶
青蛙跳台阶
一只青蛙，一次只能跳一级台阶，或者两级台阶
问：这只青蛙跳上n级台阶，有多少种跳法
递推关系:
如果这只青蛙，跳上了n级台阶，那么最后一次跳跃之前，它一定在n-1级台阶，或者n-2级台阶；
那么跳上n级台阶有多少种情况，就变成了2个子问题：
- 跳上n-1级台阶的跳法 + 2. 跳上n-2级台阶的跳法
以此类推，跳上n-1级台阶的跳法，又变成了2个子问题：
- 跳上n-2级台阶的跳法 + 2. 跳上n-3级台阶的跳法
实现方法
就是使用斐波那契数列方法实现
/**
* 青蛙跳台阶
* 一只青蛙，一次只能跳一级台阶，或者两级台阶
* 问：这只青蛙跳上n级台阶，有多少种跳法
*/
// 如果这只青蛙，跳上了n级台阶，那么最后一次跳跃之前，它一定在n-1级台阶，或者n-2级台阶
// 那么跳上n级台阶有多少种情况，就变成了2个子问题
// 1. 跳上n-1级台阶的跳法 + 2. 跳上n-2级台阶的跳法
// 以此类推，跳上n-1级台阶的跳法，又变成了2个子问题
// 1. 跳上n-2级台阶的跳法 + 2. 跳上n-3级台阶的跳法
// f(n) = f(n-1) + f(n-2)
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(2)) // 2
原文地址：https://blog.csdn.net/qq_34388186/article/details/145135794
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！