algorithm - 最短路径略有不同的解决方案

Question

我首先从算法设计（第一张图片）一书中阅读了这个 OPT 公式，我认为我非常理解这一点，无论是使用 i-1 边还是 i 边导致不同OPT(i-1,v)或OPT(i-1,w)+Cvw.

但是，当我从《算法》一书中读到同样的问题时（第二张图片从“动态编程...”开始），我很困惑，因为它消除了OPT(i-1,v)，这意味着删除路径P在大多数i-1边缘使用的条件，而只是使用OPT(i-1,w)+Cvw. 我只是想知道为什么这个公式仍然可以？有人可以解释吗？

Answer 1

I believe that the distinction is in what the DP values mean. In the first case, the value means "the best path to v using at most i edges," and in the second the value means "the best path to v using exactly i edges." Given the second of these you can directly read off the answer by looking at the final DP value, whileas in the second you'd have to look at dp(v, 0), dp(v, 1), dp(v, 2), ... dp(v, n - 1).

Hope this helps!