python - 如何获得我们拍摄外星人的时间？

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(aliens)-1 处的最后一次杀戮开始，找出第“(len(aliens)-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 添加到列表中，然后添加 parent[23] 然后添加 parent[parent[23]] 等等，直到我们达到 -1。递归只是一步反转这个链。