Java教程

带有备忘录的递归算法

本文主要是介绍带有备忘录的递归算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

暴力递归

★ leetcode原题:一只青蛙一次可以跳上1级台阶,也可以跳上2级台 阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。

  • 要计算原问题 f(10),就需要先计算出子问题 f(9) 和 f(8)
  • 然后要计算 f(9),又要先算出子问题 f(8) 和 f(7),以此类推。
  • 直到 f(2) 和 f(1),递归树才终止。

要想跳到第10级台阶,要么是先跳到第9级,然后再跳1级台阶上去;要么是先跳到第8级,然后一次迈2级台阶上去。

同理,要想跳到第9级台阶,要么是先跳到第8级,然后再跳1级台阶上去;要么是先跳到第7级,然后一次迈2级台阶上去。

要想跳到第8级台阶,要么是先跳到第7级,然后再跳1级台阶上去;要么是先跳到第6级,然后一次迈2级台阶上去。

1 普通的递归算法

class Solution {
    public int numWays(int n) {
    if(n == 1){
        return 1;
    }
     if(n == 2){
        return 2;
    }
    return numWays(n-1) + numWays(n-2);
    }
}

2 带备忘录的递归算法

带备忘录的递归算法,子问题个数=树节点数=n,解决一个子问题还是O(1),所以带备忘录的递归算法的时间复杂度是O(n)。接下来呢,我们用带备忘录的递归算法去撸代码,解决这个青蛙跳阶问题的超时问题咯~,代码如下:

public class Solution {
    //使用哈希map,充当备忘录的作用
    Map<Integer, Integer> tempMap = new HashMap();
    public int numWays(int n) {
        // n = 0 也算1种
        if (n == 0) {
            return 1;
        }
        if (n <= 2) {
            return n;
        }
        //先判断有没计算过,即看看备忘录有没有
        if (tempMap.containsKey(n)) {
            //备忘录有,即计算过,直接返回
            return tempMap.get(n);
        } else {
            // 备忘录没有,即没有计算过,执行递归计算,并且把结果保存到备忘录map中,对1000000007取余(这个是leetcode题目规定的)
            tempMap.put(n, (numWays(n - 1) + numWays(n - 2)) % 1000000007);
            return tempMap.get(n);
        }
    }
}
这篇关于带有备忘录的递归算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!