algorithm - 动态规划寻找最小路径

Question

我在为这个 DP 问题设计解决方案时遇到问题

假设你想从 A 城市到 B 城市旅行。途中有 n 个中途停留点，你有很多选择可以选择每个中途停留点的酒店。所涉及的成本是在中途停留点到某个酒店的旅行费用(我们称之为 tij，其中 i 是当前的中途停留地，j 是下一个)和在中途停留地 j 的酒店住宿费用(我们称之为 sj)。设计一个动态规划算法来选择最佳路线和城市 B 的旅馆，使整个行程的成本最小化。分析其正确性和运行时间。

Answer 1

这是一个可能正确的算法:定义停靠点为a1,a2,a3,a4,a5,a6.....an，每个停靠点的最小成本为c1,c2,c3,c4,c5...cn

第一站。计算从城市 A 到 a1 的路线成本，并将其存储在 c1 中。

第二站。计算从 A 到 a2 的路线成本，并计算从 a1 到 a2 的路线成本加上 c1。选择较小的代价存入c2

第三站。计算从 A 到 a3 的成本，a1 到 a3 的成本加上 c1，以及 a2 到 a3 的成本加上 c2。选择最小的代价存入c3

........

最后，我们可以找到cn+1，即从A到B的路径的最小成本，与上述步骤相同

动态表达式为 ci=min(c1+t(1,i),c2+t(2,i),c3+t(3,i),....,c(i-1)+ t(i-1,i))

我们尝试所有可能的路线到每个站点并找到最小的成本，因此答案是我们选择的路线最小化的原因

该算法运行时间为O(n^2)，考虑构建一个大小为n*n的二维数组