發現通過陣列（遞歸）最廉價的路徑

-1

發現通過使用遞歸的數組最廉價的路徑。例如，如果我有一個數組[0,1,3,4,1]我從數值0開始。現在我有2個選項，我可以跳到索引2或者只是移動到索引1.在這種情況下，我會跳轉索引2（值3）的權利，然後跳轉到索引4（值1），因爲3 + 1 = 4，這將是最便宜的方式通過陣列。

我試圖將移動索引值與跳轉索引值進行比較，並查看哪個最小，但在這種情況下不起作用，因爲如果我將移動值（1）與跳轉值（3）進行比較，則1是最小的，我的程序會把它當作正確的路徑，但實際上它不是，3是更好的選擇。

謝謝您花時間幫忙！

來源

2015-10-18 stacker

解釋你的理性跳躍到這些指數。 – Makoto

對不起。爲此，我們只能跳轉或移動。前進= 2個空格，前進= 1個空格。所以爲了找到最便宜的路徑，我會跳到第3個值，然後跳到第1個值。所有其他可能性都更「昂貴」。 – stacker

它仍然沒有道理。你應該描述遞歸在這裏扮演什麼部分，以及你用什麼理由跳轉（它是數組中的值，就像我想的那樣）。 – Makoto

您可以使用動態編程來解決這個問題。比方說，我們創建一個數組dp，其中dp [i]表示在位置i處達到的最低成本。我們可以通過填寫此陣高達輸入的尺寸如下：

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個位置無論是先前的位置，採取一招或I-2通過採取2.So的跳躍以這種方式達到你可以找到達到最終位置的最低成本。所以dp [len]將是你到達最後位置的最低成本。還有一個類似的問題here

來源

2015-10-18 18:54:52 Khatri

你也可以使用遞歸來解決這個問題，但它會花費指數的時間。所以我寫了一個O（n）方法。 – Khatri

絕對讚賞O（n）的方法，但我目前正在閱讀遞歸的一章，這個問題已經讓我困擾了很長時間。 – stacker

然後你可以使功能爲： 'int recurse（vector ＆arr，int cur，int cost）' 其中cur表示你需要從哪個位置到達結尾，基本條件將是cur == len和cost是否是達到目標位置的最低成本。 – Khatri

發現通過陣列（遞歸）最廉價的路徑

回答

相關問題