我一直在完成动态编程挑战。我正在尝试完成以下内容，但在当前实现中得到了错误的答案
https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/tutorial/
这背后的想法是：
计算列表中葡萄酒的最高价格。
你每年只能喝一瓶酒
每种葡萄酒只能从葡萄酒列表的末尾或开头开始挑选。
每种葡萄酒的价格由葡萄酒*年份决定
一岁开始
当我在函数外部定义缓存时（即，在我的解决方案中，不作为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
在这种情况下，我如何在不使用inout参数的情况下使用Memoization，更正上面的代码以给出50的答案，而不是上面所写的不正确的49。
最佳答案
您的问题不在于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
关于swift - 快速动态编程，无需在缓存中使用inout，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54546801/