swift - 动态规划 Fibonacci Swift

Question

我试图将下面的实现隐藏到 Swift 并且遇到了困难:

var mem = [];
var fibRecursiveMem = function (n) {
    if (mem[n]) return mem[n];
    if (n<=2) mem[n] = 1;
    else {
        mem[n] = fibRecursiveMem(n-1) + fibRecursiveMem(n-2);
    }
    return mem[n];
} 

来自:https://dev.to/rattanakchea/dynamic-programming-in-plain-english-using-fibonacci-as-an-example-37m1

我在 Swift 中的实现:

var mem = [Int]()
func fib (_ num: Int) -> Int {
    if (mem.count - 1 > num) {
        return mem[num]
    }
    if (num<=2) {mem[num] = 1}
    else {
        mem[num] = fib(num-1) + fib(num-2)
    }
    return mem[num]
}

产生索引超出范围的错误。

现在我想遵循原始算法的一般逻辑。我在翻译中做错了什么？

Answer 1

在这种情况下，用字典来实现内存会更好:

var mem = [Int: Int]()
func fib (_ num: Int) -> Int {
    if let cached = mem[num] {
        return cached
    }

    let result: Int

    if (num <= 2) {
        result = 1
    }
    else {
        result = fib(num - 1) + fib(num - 2)
    }

    mem[num] = result
    return result
}

在 javascript 中，数组和字典之间的区别相当小。即使 mem 被声明为数组，它实际上也被用作字典。

要使用数组，我们必须确保始终正确地append:

var mem = [0, 1, 1] // prefill initial values for 0, 1, 2
func fib (_ num: Int) -> Int {
    if num < mem.count {
        return mem[num]
    }

    let result = fib(num - 1) + fib(num - 2)
    // the recursion has already appended all previous values
    mem.append(result)

    return result
}