algorithm - 动态规划问题，找到对商店的最佳访问

Question

假设我们有一个商店列表，这些商店在访问时包含一些价值。例如 store_value = [2,4,9,1,4,2]。

从一个商店跑到另一个商店收集价值有一些成本，例如run_cost = [0,1,2,3,1,2]。也就是说，如果我在商店 i = 3（不是 0 索引）处收集价值 9，它将具有成本 2，这意味着由于所需的成本，我将无法访问之前的 2 家商店。考虑它在运行存储 i 之前的休息量。

现在使用动态规划，我们可以说 V(x,i)，其中 V(0,i) 是在第一个 i 存储之后可获得的最大值，如果我们不运行存储 i。V(1,i) 是第一个 i 存储后可获得的最大值，如果我们确实运行存储 i。

从商店 i = 1..6 运行的 P(0,i) 和 P(1,i) 会是什么样子？

我尝试运行算法，但有些东西告诉我我做错了什么。据我所知：

P(0,1) = 0, P(1,1) = 2

从这里开始，我认为我错了： P(0,2) = 2, P(1,2) = 4 ... 等等

如果有人可以帮助我理解我应该如何思考这个问题，我会非常感激。

标签： algorithmdynamic-programming

Answer 1

一个更简单的公式是定义V(i)为可以通过 stores 实现的最大值1..i。那么递归定义是：

V(i) = max(
           V(i - 1),                                //do not visit store i
           store_value[i] + V(i - run_cost[i] - 1)  //visit store i
       )

run_cost在 .时需要注意一些0。