算法疑难(js实现)---4、跳台阶（记忆化递归）

一、总结

一句话总结：

跳台阶的问题就是一个非常标准的递归类型的问题，找到递推表达式，写递归就非常简单了，由于递归会多次重复的求中间状态的结果，造成计算的浪费，所以我们可以把中间状态的结果保存下来，也就是用记忆化递归来做

//1、递归写法
function jumpFloor(n){
    if(n==1) return 1;
    else if(n==2) return 2;
    return jumpFloor(n-1)+jumpFloor(n-2);
}

//2、记忆化递归（保存中间结果）
//对于cache数组，cache[n]就表示缓存的f(n)的结果
let cache=[,1,2];
function jumpFloor2(n){
    //也就是我们在找f(n)的值的时候，如果缓存里面有，直接用缓存
    if(cache[n]!==undefined) return cache[n];
    return cache[n]=jumpFloor2(n-1)+jumpFloor2(n-2);
}

1、记忆化递归是什么？

将递归的中间结果保存下来，需要中间结果的时候去缓存里面看，如果有就直接用，就不用重新计算，从而节约性能，也就是拿空间换时间

//1、递归写法
function jumpFloor(n){
    if(n==1) return 1;
    else if(n==2) return 2;
    return jumpFloor(n-1)+jumpFloor(n-2);
}

//2、记忆化递归（保存中间结果）
//对于cache数组，cache[n]就表示缓存的f(n)的结果
let cache=[,1,2];
function jumpFloor2(n){
    //也就是我们在找f(n)的值的时候，如果缓存里面有，直接用缓存
    if(cache[n]!==undefined) return cache[n];
    return cache[n]=jumpFloor2(n-1)+jumpFloor2(n-2);
}

2、递归类型的题目的注意点？

1、递归的终止条件

2、递归对应的递推表达式

二、跳台阶（记忆化递归）

博客对应课程的视频位置：4、跳台阶（记忆化递归）
https://www.fanrenyi.com/video/20/240

 1 <!DOCTYPE html>
 2 <html lang="en">
 3 <head>
 4     <meta charset="UTF-8">
 5     <title>跳台阶（记忆化递归）</title>
 6 </head>
 7 <body>
 8 <!--
 9 
10 需求：
11 一只青蛙一次可以跳上1级台阶，也可以跳上2级。
12 求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
13 
14 递归类型的题目
15 
16 一步直接跳到第n级台阶，有哪些方式
17 1、在第n-1级台阶处跳1级
18 2、在第n-2级台阶处跳2级
19 
20 f(n)表示青蛙跳上一个n级的台阶总共的跳法种数
21 f(n)=f(n-1)+f(n-2)
22 
23 递归类型的题目的注意点：
24 1、递归的终止条件（n==1,有一种跳法,n==2，2种跳法）
25 2、递归对应的递推表达式
26 
27 -->
28 <script>
29     //1、递归写法
30     function jumpFloor(n){
31         if(n==1) return 1;
32         else if(n==2) return 2;
33         return jumpFloor(n-1)+jumpFloor(n-2);
34     }
35     console.log(jumpFloor(3));
36     console.log(jumpFloor(4));
37     console.log(jumpFloor(5));
38     console.log(jumpFloor(10));
39 
40     //2、记忆化递归（保存中间结果）
41     //对于cache数组，cache[n]就表示缓存的f(n)的结果
42     let cache=[,1,2];
43     function jumpFloor2(n){
44         //也就是我们在找f(n)的值的时候，如果缓存里面有，直接用缓存
45         if(cache[n]!==undefined){
46             //console.log(n,cache[n]);
47             return cache[n];
48         }
49         return cache[n]=jumpFloor2(n-1)+jumpFloor2(n-2);
50     }
51     console.log(jumpFloor2(10));
52     console.log(cache);
53 
54 </script>
55 
56 </body>
57 </html>