给出了一系列费用。你可以向前跳两次,也可以向后跳一次。如果你使用特定的索引,则必须将成本加到总计中。找到穿越阵列或到达阵列末端所需的最低成本。
输入:
5 (Number of elements in the array)
[9,4,6,8,5] (Array)
1 (Index to start)
输出:
12
说明:我们从索引1开始,跳至3,然后跳出,总成本为8 + 4 = 12。
我们如何为此构建DP解决方案?
你可以将递归程序与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];
}
此递归将无法解决。进入无限循环-可以轻松地检查一个由5个元素组成的小数组并展开堆栈。