如何獲得我們拍攝外星人的時間？

Question

根據這thread，我試圖用python編寫算法。

這裏是我的代碼：

def shoot(aliens): 

    s=[0]*1000 
    s[0]=0 
    s[1]=1 
    num=len(aliens) 
    for j in xrange(2,num): 
     a=[0]*1000 
     for i in xrange(0,j): 
      a[i]=s[i]+min(int(aliens[j]),f[j-i]) ## possible tries 
     s[j]=max(a)      ##f[i] is the i-th finonacci number 

    return s[len(aliens)-1] 

它的工作通過展示最大的外國人遭到破壞。 但是，我想打印出他們拍攝外星人的時間。 我的想法是從最後一次擊殺，這是在len（外星人）-1，並找出最後一次拍攝是在「（len（外星人-1））」拍攝之前。然後繼續做同樣的事情，直到我們到達第一次拍攝。

爲了做到這一點，我存儲了所有可能的嘗試，並將最後一次拍攝與他們進行比較以找到最後一次拍攝，但運行時間會很長，並顯示錯誤的結果。 林不知道它是否正確，但我試圖實施它，但我失敗了。

有沒有人有這樣的想法？ 謝謝！ PS：請問我你是否得不到我寫的東西。另外，我不想從上面的線索複製問題，因爲它很長。如果它困擾你，我很抱歉。

Answer 1

我不知道你在哪裏得到了從斐波那契數（原始遞歸關係，有（j - I）^ 2）

無論如何，最簡單的方法是跟蹤父陣列的，而這樣做dp。例如：

def getTimes(aliens): 
    n = len(aliens) 
    dp = [0] * n #your s array. I'm just used to using dp for dp tables 
    parent = [-1] * n 
    dp[1] = 1 
    for i in range(2, n): 
     max = 0; #assuming there can't be a negative number of aliens. 
     for j in range(0, i): 
      x = dp[j] + min(int(aliens[i]), (i - j) * (i - j)) 
      if(x >= max): 
       max = x 
       parent[i] = j 
     dp[i] = max; 
    times = getTimesRec(n - 1, [], parent) 
    return times 

def getTimesRec(i, times, parent): 
    if(i == -1): 
     return times 
    getTimesRec(parent[i], times, parent) 
    times.append(i) 
    return times 

我沒有測試過這個，但它背後的想法應該沒問題。基本上，每當你找出最後一個外星人被槍殺的時候，你都要在父親陣列中追蹤它。然後，您可以從最後開始，按遞歸順序（如圖所示）或使用堆棧以相反順序將時間存儲到列表中。

通過使用類似於最長增長子序列的二分查找，您也可以使O（nlogn）運行。我懶得考慮如何去做。

編輯：希望我能澄清一些混亂。給定時間範圍時，前一個鏡頭髮生時，所有父級陣列所做的都是存儲。

因此，例如，讓我們說，你拍的時候4，19和23這意味着父陣列是這樣的：

parent[23] = 19 
parent[19] = 4 
parent[4] = -1 

所以給這個數組，我們可以計算出相反的順序只需將23添加到列表中，然後再添加父母[23]，然後再添加父母[父母[23]]，直到我們達到-1。遞歸就是在這裏一步一步地扭轉這條鏈。