如何获取我们击毁外星人的时间？

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）第次射击之前。然后继续做同样的事情直到第一次拍摄。在

为此，我存储了所有可能的尝试，并将最后一次拍摄与最后一次拍摄进行比较，以找到第二次最后一次拍摄，但运行时间太长，结果显示错误。 我不确定这是不是正确，但我试图实施它，但我失败了。在

有人对此有什么想法吗？ 谢谢您！在

附言：如果你不明白我写的，请问我。另外，我不想复制上面的问题，因为它很长。如果你觉得不舒服，我很抱歉。在

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拍。这意味着父数组如下所示：

^{pr2}$

因此，给定这个数组，我们可以计算出时间的倒序，只需将23加到一个列表中，然后再加上parent[23]，然后再加上parent[23]]，直到达到-1。递归只是为了在一个步骤中反转这个链。在