PellNumbers 通过递归。尝试实现记忆向量失败

Question

我试图通过递归和 HashMaps 制作更高效的 PellNumbers 方法，但 return 很糟糕。它由 Pn-1（n-1 行的 PellNumber）关闭。

我的意思是对于 7，return 应该是 169，但它是 239（相差 70，即 P6）。

有没有办法让这个东西起作用？经过几次计算，我想存储值以便以后访问它们。

public class PellNumbers {

private static final Map<Long, Long> pellNumbers = new HashMap<Long, Long>();
static {
    pellNumbers.put(0L,1L);
    pellNumbers.put(1L, 1L);
}

public static long getPellNumber(long n) {

    if (pellNumbers.containsKey(n)) return pellNumbers.get(n);
    if (n<2) return n;
    pellNumbers.put(n, 2*getPellNumber(n-1) + getPellNumber(n-2));  
    return 2*getPellNumber(n-1) + getPellNumber(n-2);       
}

Answer 1

您没有正确初始化 Map。佩尔号码以 0 开头 (0, 1, 2, 5, 12, 29, 70, 169 ...)

static {
    pellNumbers.put(0L,0L);
    pellNumbers.put(1L, 1L);
}

PellNumbers 通过递归。尝试实现记忆向量失败

PellNumbers via recursion. Failed attempt to implement memorizing vector

java

memory

recursion

memory-efficient