python - 找到到达数组末尾的最小成本
问题描述
给出了一系列成本。您可以向前跳两下或向后跳一跳。如果您登陆特定指数，则必须将成本添加到总成本中。找出穿过阵列或到达阵列末端所需的最小成本。
输入：
5 (Number of elements in the array)
[9,4,6,8,5] (Array)
1 (Index to start)
输出：
12
解释：我们从索引 1 开始，跳到 3 再跳出来，总成本为 8+4=12。
我们如何为此构建 DP 解决方案？
解决方案
您可以使用Dijkstra 的算法（图）来解决这个问题。
按着这些次序：
1.通过将 第 i 个索引的节点与第(i-1) 个和第(i+2) 个索引的节点及其成本（如果可能）连接起来，生成加权有向图。
2.应用 Dijkstra 算法找到初始节点（索引）和目标节点（索引）之间的最短路径。