动态编程斐波那契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 = [1, 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
}