找到到达数组末尾的最小成本

Question

给出了一系列成本。您可以向前跳两下或向后跳一跳。如果您登陆特定指数，则必须将成本添加到总成本中。找出穿过阵列或到达阵列末端所需的最小成本。

输入：

 5 (Number of elements in the array)

[9,4,6,8,5] (Array)

1 (Index to start)

输出：

 12

解释：我们从索引 1 开始，跳到 3 再跳出来，总成本为 8+4=12。

我们如何为此构建 DP 解决方案？

原文由 Tavish Jain 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您可以将递归程序与 Dp 一起使用

//cur will the final destination that is last element at first execution
//N is no of elements
int Dp[N]={0};
Dp[0]=element[0]; //initial condition
least_path(cur,*elements,N)
{
   if(cur>N-1 || cur<0)
     return INT_MAX;
  if(Dp[cur])
   return Dp[cur];
  int temp1=least_path(cur-2,*elements,N)+element[cur];
  int temp2=least_path(cur+1,*elements,N)+element[cur];
  Dp[cur]=min(temp1,temp2);
  return Dp[cur];
}

原文由 Arjun U S 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

您可以使用 Dijkstra 的算法（图） 来解决这个问题。

按着这些次序：

1. 通过将 第 i 个索引 的节点与第 (i-1) 和 (i+2) 索引的节点及其成本（如果可能）连接起来， _生成加权有向图_。

2. 应用 Dijkstra 算法 _找到初始节点（索引）和目标节点（索引）之间的最短路径_。

原文由 Yash Shah 发布，翻译遵循 CC BY-SA 4.0 许可协议