通過數組的最低成本

Question

問題

給定一個長度爲[N]的數組，您必須從數組[0]開始並遍歷到結尾。您可以根據數字總和較低來移動一個或兩個位置，即數組[0] - >數組[1]或數組[0] - >數組[2]。這將會一直重複到最後，並且必須包含array [N]。

[1，10，3,8，4]導航 最便宜的方法是通過陣列= 8 [0] +陣列[2] +陣列[4]

我的當前的解決方案：

int totalCost = 0 
totalCost += array[0] 
int i = 1; 
while (i < array.length) 
{ 
    if (i + 1 < array.length) 
    { 
     int sum1 = totalCost + array[i]; 
     int sum2 = totalCost + array[i + 1]; 
     if (sum1 < sum2) 
     { 
      totalCost += array[i]; 
      i++; 
     } 
     else 
     { 
      totalCost += array[i + 1]; 
      i += 2; 
     } 
    } 
    else 
    { 
     totalCost += array[i]; 
     i++; 
    } 
} 

這似乎是大多數陣列工作...問題進場其中，如果早跳導致大數目，但允許通過更好最終導致在一個較低的數字陣列進行進一步的跳躍。我不知道如何解決這個問題。

Answer 1

你的做法是行不通的，因爲你嘗試在下一步的行動決定，當你在某個元素。要點是，你通常不能決定你的下一步行動，直到你知道所有元素值直到數組結尾的第二個元素。

不僅在計算機科學，但通常更容易尋找到過去和學習，而不是展望未來和預測。因此，只要歷史數據能夠解決問題或子問題，就不要試圖用未來的期望來解決問題。

現在，讓我們看看如何可以應用到你的問題。

如果您位於陣列中的位置爲i，您所做的是試圖通過查看可能的後續步驟並確定其中一個步驟來預測正確的方式，但這不可靠。所以讓我們假設你處於i的位置，你不想知道下一步該去哪裏，而是你問「什麼是最好的（成本效益）的方式來達到目前的位置和多少成本？」。

對於第一位置i=0，這是微不足道的。您通過啓動算法達到此位置並且成本等於a[0]的值。

對於第二位置i=1，它也是微不足道的。您可以按照步驟1（小步）或2（大步）移動，但在此特定情況下，只能進行一小步操作，因此您可以通過從位置i=0到達i=1，成本等於達到i=0加成本位置的值爲i=1。

對於所有後續位置i>1，需要做出決定，無論是通過一小步還是一大步達到當前位置。如果通過一小步達到當前位置，則其成本計算爲達到i-1加上位置i的值的成本。其他情況下，如果當前頭寸達到大步，則其成本計算爲達到i-2加上頭寸i的價值。爲了以最低的成本達到i的位置，通過比較其相關成本和選擇最小值來決定小步驟還是大步驟。

當到達數組末尾時，將計算到達每個位置的成本和步驟，並且可以返回到達最後位置的成本。

如果你只需要最小的成本，而不是實際的路徑，那麼下面應該工作（與C相關的僞代碼）：

costs[array.size] = { 0 }; 

for (i = 0; i < array.size; ++i) 
{ 
    if (i > 1) costs[i] = array[i] + min(costs[i-1], costs[i-2]); 
    else if (i > 0) costs[i] = array[i] + costs[i-1]; 
    else costs[i] = array[i]; 
} 

result = costs[array.size - 1]; 

它基本上是說：在某個時刻i可以通過正在添加完成從前一點或從前2點開始。如果前兩個點的成本已經計算出來，那麼決定就像取前兩個點成本的最小值並加上當前點成本一樣簡單。

除了具有所有子成本的數組之外，您甚至可以使用總共3個變量（丟棄代表i-2以下的索引的子成本），但是不能從子重構構建路徑-costs。

Answer 2

var c = new List<int>(); 
for (int i = 0; i < a.Length - 1;) 
{ 
    c.Add(i); 
    if (i < a.Length - 2 && a[i + 2] < a[i + 1]) 
     i += 2; 
    else 
     i += 1; 
} 
c.Add(a[a.Length - 1]); 

Answer 3

我忽略了以前的選擇影響未來總和的可能性。我同意這是在某種程度上的人工智能。

解決方案我修改爲。

int total = 0; 
cost += array[0]; 

int i = 0; 
while (i < array.Length - 1) 
{ 
    if ((array[i+1] + total) < array[i+2] + total) && (i != array.Length - 3)) 
    { 
     total += array[i + 1]; 
     i++; 
    } 
    else 
    { 
     total += array[i + 2]; 
     i += 2; 
    } 
} 

我不得不第二添加到最後一個元素檢查，因爲如果迭代器降落在第二到最後，沒有理由要檢查哪一個是較低的，因爲我不得不選擇最後一個不分。