17.动态规划之青蛙跳台阶代码实现（JavaScript版）

佚名 5年前 (2020-07-02) 算法 880人围观抢沙发百度已收录

动态规划之青蛙跳台阶

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
//一只青蛙，一次只能跳一级台阶或两级台阶，问这个青蛙跳上n级台阶有多少种跳法？
//核心思想：fn(n) = fn(n - 1) + fn(n - 2)
function jump(n){
    if(n <= 0){
        return 0;
    }else if(n == 1){
        return 1;
    }else if(n == 2){
        return 2;
    }

    return jump(n - 1) + jump(n - 2);
}

console.log(jump(4));

//一只青蛙，一次只能跳一级台阶或两级台阶或n级台阶，问这个青蛙跳上n级台阶有多少种跳法？
//核心思想：fn(n) = fn(n - 1) + fn(n - 2) + ... + fn(2) + fn(1)
function jump2(n){
    if(n <= 0){
        return 0;
    }else if(n == 1){
        return 1;
    }else if(n == 2){
        return 2;
    }
    var result = 0;
    for(var i = 1; i < n; i++){
        result += jump2(n - i);
    }
    
    return result + 1;//+1表示从0级台阶直接跳上n级台阶
}

console.log(jump2(3));
    </script>
</body>
</html>