找到到达阵列末端的最小成本

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解决方案？

Answer 1

基于DP的解决方案-以自下而上的方式填充一维成本阵列。包括两个步骤：

1. 在达到指数i时，检查并更新成本，如果我们可以通过从指数i 1达到它来改进成本

时间复杂度：O（n），其中n是输入数组的长度。

    # Python3 snippet  
    # Inputs: startIndex, array A of non negative integers
    # Below snippet assumes A has min length 3 beginning from the startIndex. We can handle smaller arrays with base cases - thus, not listing them out explicitly

    import math

    costs = [math.inf] * len(A)
    costs[startIndex] = A[startIndex]   
    costs[startIndex+1] = A[startIndex] + A[startIndex+1] + min(A[startIndex+1], A[startIndex-1] if startIndex >=0 else A[startIndex+1])

    N = len(A)
    for i in range(startIndex, N):
        if i+1 < N:
            costs[i] = min(costs[i], costs[i+1] + A[i])
        if i + 2 < N:                 
            costs[i+2] = costs[i] + A[i+2]

    print(min(costs[-1], costs[-2]))

Answer 2

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

遵循以下步骤：

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

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

Answer 3

您可以将递归程序与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];
}