通过数组找到最便宜的路径（递归） [英] find cheapest path through array (recursion)

问题描述

我目前正在从事递归工作，但我一直陷于这个问题：

I'm currently working on recursion and i keep getting stuck at this question:

使用递归查找数组中最便宜的路径。例如，如果我有一个数组[0,1,3,4,1]我从值0开始。现在我有2个选项，我可以跳转到索引2或只是移到索引1。在这种情况下，我会跳转右移到索引2（值3），然后跳到索引4（值1），因为3 + 1 = 4，这将是遍历数组的最便宜的方法。

Find the cheapest path through an array using recursion. for example, if i had an array [0,1,3,4,1] i start at the value 0. Now i have 2 options i could jump to index 2 or just move to index 1.In this case i would jump right to index 2 (value 3) then jump to index 4 (value 1) because 3+1= 4 and that would be the cheapest way through the array.

I试图将移动索引值与跳转索引值进行比较，看看哪一个最小，但在这种情况下将不起作用，因为如果我将移动值（1）与跳转值（3）进行比较，则1最小，而我的程序会将其作为正确的路径，但实际上并非如此，而3是更好的选择。

I've tried to compare the move index value with the jump index value and see which is smallest but in this case that would not work because if i compare move value (1) with jump value (3), 1 is smallest and my program would take that as the correct path when in reality it is not and the 3 was a better option.

感谢您抽出宝贵的时间来帮助您！

Thank you for taking the time to help!

推荐答案

您可以使用动态编程来解决此问题。假设我们创建了一个数组dp，其中dp [i]代表min到达位置i的费用。
我们可以使用以下命令来填充该数组，直到输入的大小：

You can solve this problem using dynamic programming.Let's say we create one array dp, in which dp[i] represents min cost to reach at position i. We can fill this array upto size of input using following:

for(i=1;i<=len;i++) 
   //we can reach at current position either by i-1 or by i-2
   //choose one which gives minimum cost and +arr[i] cost of current position
   dp[i] = min(dp[i-1],dp[i-2])+arr[i]

我们可以通过向前移动一个位置来到达第i个位置，或者通过跳跃2来通过i-2到达第i个位置，因此可以找到到达最终位置的最小成本。 [len]是您达到最终排名的最低费用。
此处

we can reach at ith position either by previous position by taking one move or by i-2 by taking a jump of 2.So in this way you can find the minimum cost to reach the final position.So dp[len] will be your minimum cost to reach at last position. There is one similar problem here

这篇关于通过数组找到最便宜的路径（递归）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！