使用记忆的 Tribonacci 实现：运行时错误

Question

大家好，我试图在 java 中实现 tribonaci 的解决方案，你们中的许多人可能都熟悉动态程序迷你课程中的这个 leetcode 任务。基本上在 tribonaci t0 = 0 t1 = t2 = 1 和 tn = t(n - 3) + t(n-2) + t(n-1) 内。我试图通过使用 hasmap 和记忆（从上到下）的递归解决方案来实现它。但是，当我运行代码时，出现运行时错误。任何人都可以帮我查明来源吗？提前谢谢你

class Solution {
private HashMap<Integer,Integer> memo = new HashMap<Integer,Integer>();
private int n;
private int dp(int i){
    if (n == 0) return 0;
    if (n == 1 || n == 2) return 1;
    if(!memo.containsKey(i)){
        memo.put(i,dp(i - 1) + dp(i - 2) + dp(i - 3));
    }
    return memo.get(i);
}
public int tribonacci(int n) {
    this.n = n;
    return dp(n);
}

}

Answer 1

问题是您没有达到递归的 end/bottom。你写了它，tribonacci 是 - tn = t(n - 3) + t(n-2) + t(n-1)，但在你的代码中你做相反的事情 - dp(n) + dp(n + 1) + dp(n + 2)，而不是对前 3 个值求和，而是对当前值和 2 个下一个值求和。想象一下——您需要向后退以获取已经计算出的值，但在您的代码中您前进到下一个值，但它们并不存在。这就是导致递归无底并连续到 Whosebugerror.

的原因

这里是代码，经过修改和简化。

public class Tribonnaci {

  private final HashMap<Integer,Integer> memo;

  public Tribonnaci() {
    this.memo = this.initMap();
  }

  private HashMap<Integer, Integer> initMap() {
    //init map, this will be bottom of your recursion
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(0, 0);
    map.put(1, 1);
    map.put(2, 1);
    //also, cleaner, your bottom is the memoized values
    //not combination of it and if checks
    return map;
  }

  private int calculateNthTribonacci(int n){
    Integer result = this.memo.get(n);
    //if result is null, that means it has not been calculated before
    if (result == null) {
      //sum the three previous values from tribonnaci sequence
      result = this.calculateNthTribonacci(n - 1) + this.calculateNthTribonacci(n - 2) + this.calculateNthTribonacci(n - 3);
      //save it in memo
      this.memo.put(n, result);
    }
    return result;
  }

  public int tribonacci(int n) {
    return calculateNthTribonacci(n);
  }
}

编辑：好的，现在问题是实例变量private int n;。您不使用实例变量来检查递归 bottom

if (n == 0) return 0;
if (n == 1 || n == 2) return 1;

到达底部时必须检查方法参数。递归是在该方法内部调用相同的方法，但给它不同的参数。在您的情况下，这是 i:

private int dp(int i)

这就是为什么您需要检查 i 的值以到达递归底部并删除实例变量 n。像这样：

public class Tribonnaci {

    private HashMap<Integer, Integer> memo = new HashMap<Integer, Integer>();

    private int dp(int i) {
        if (i == 0) return 0;
        if (i == 1 || i == 2) return 1;
        if (!memo.containsKey(i)) {
            int prev = dp(i - 1);
            int prevPrev = dp(i - 2);
            int prevPrevPrev = dp(i - 3);
            int value = prev + prevPrev + prevPrevPrev;
            memo.put(i, value);
        }
        return memo.get(i);
    }

    public int tribonacci(int n) {
        return dp(n);
    }
}

我故意写得冗长，调试了几次以更好地理解递归的工作原理。

使用记忆的 Tribonacci 实现：运行时错误

Tribonnaci implementation using memoization: Runntime error

java

dynamic

memoization

fibonacci