Быстрое динамическое программирование без использования inout для кеша

Question

Я выполняю задачи динамического программирования.Я пытаюсь завершить следующее, но получаю неправильный ответ с моей текущей реализацией

https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/tutorial/

Идея этого заключается в следующем:

РассчитатьМаксимальная цена вина в списке.

Вы можете взять только одно вино на каждый год

Каждое вино можно собирать только с конца или начала списка вин.цена каждого вина определяется вином * year

год начинается с 1

Когда я определяю кэш вне функции (т.е. НЕ передается как параметр inout, как в моемрешение здесь: https://gist.github.com/stevencurtis/c265e523323be73ec823084b0707a426) скорее мое решение, как показано ниже, дает неправильный ответ (49, а не 50)

var mem = [[Int]]()

func dynamicMotivation (_ wines: [Int] ) -> Int {
    mem = Array(repeating: Array(repeating: 0, count: wines.count), count: wines.count)
    return motivationD(wines, year: 1, ptr1: 0, ptr2: wines.count - 1, 0)
}

func motivationD(_ wines: [Int], year: Int, ptr1: Int, ptr2: Int, _ runningTotal: Int) -> Int {
    if (ptr1 > ptr2) {return runningTotal}
    if mem[ptr1][ptr2] != 0 {
        return mem[ptr1][ptr2]
    }
    let maxProfit = max(
        motivationD(wines, year: year + 1, ptr1: ptr1 + 1, ptr2: ptr2, runningTotal + year * wines[ptr1])
        ,
        motivationD(wines, year: year + 1, ptr1: ptr1, ptr2: ptr2 - 1, runningTotal + year * wines[ptr2])
    )
    mem[ptr1][ptr2] = maxProfit
    return maxProfit
}

dynamicMotivation([2,3,5,1,4]) // 50 is the optimal solution here

Как я могу использовать Memoization в этом случае без использования параметра inout, исправляя кодвыше, чтобы дать ответ 50 вместо неправильного 49, как написано выше.

Answer 1

Ваша проблема не mem и не передается ли она как inout.Ваша проблема в параметре runningTotal.Я удалил этот параметр, чтобы он соответствовал алгоритму, указанному в ссылке, и теперь он возвращает правильный результат.

var mem = [[Int]]()

func dynamicMotivation (_ wines: [Int] ) -> Int {
    mem = Array(repeating: Array(repeating: 0, count: wines.count), count: wines.count)
    return motivationD(wines, year: 1, ptr1: 0, ptr2: wines.count - 1)
}

func motivationD(_ wines: [Int], year: Int, ptr1: Int, ptr2: Int) -> Int {
    if (ptr1 > ptr2) { return 0 }
    if mem[ptr1][ptr2] != 0 {
        return mem[ptr1][ptr2]
    }

    let maxProfit = max(
        motivationD(wines, year: year + 1, ptr1: ptr1 + 1, ptr2: ptr2) + year * wines[ptr1]
        ,
        motivationD(wines, year: year + 1, ptr1: ptr1, ptr2: ptr2 - 1) + year * wines[ptr2]
    )
    mem[ptr1][ptr2] = maxProfit
    return maxProfit
}

dynamicMotivation([2,3,5,1,4]) // 50 is the optimal solution here

50