棋盘算法实现

Question

def Checker(n):
    p = [[7,3,5,6,1],[2,6,7,0,2],[3,5,7,8,2],[7,6,1,1,4],[6,7,4,7,8]]  #profit of each cell
    cost = [[0 for j in range(n)] for i in range(n)]
    w = [[0 for j in range(n)] for i in range(n)]   #w[i, j] store the column number (j) of the previous square from which we moved to the current square at [i,j]
   for j in range(1,n):
       cost[1][j] = 0
   for i in range(2,n):
        for j in range(1,n):
            max = cost[i-1][j] + p[i-1][j]
            w[i][j] = j
            if (j > 1 and cost[i-1][j-1] + p[i-1][j-1] > max):
                max = cost[i-1][j-1] + p[i-1][j-1]
                w[i][j] = j-1
            if (j < n and cost[i-1][j+1] + p[i-1][j+1] > max):
                max = cost[i-1][j+1] + p[i-1][j+1]
                w[i][j] = j+1
            cost[i][j] = max
            print cost[i][j]
    maxd = cost[1][1]
    maxj = 1
    for j in range(2,n):
        if cost[1][j] >maxd:
            maxd = cost[1][j]
            maxj = j
    print "Maximum profit is: ",maxd
    printsquares(w,n,maxj)

def printsquares(w,i,j):
    if i == -1:
        return
    print "Square at row %d and column %d"%(i,j)
    printsquares(w,i-1,w[i][j])

if __name__ == '__main__':
    print "5*5 checker board problem"
    n = 5
    Checker(n)

以上程序是棋盘算法在python中的实现。 运行上述代码时，将显示以下错误：

if (j < n and cost[i-1][j+1] + p[i-1][j+1] > max): IndexError: list index out of range

我做错了什么？有人会提出解决方案吗？在

Answer 1

在Python中，列表从1开始，而列表从0开始，这看起来像是在尝试使用一种语言的算法。据我所查，你永远不会访问cost[i][0]。在

Answer 2

你很想这么做：

L = range(5)
print L[5+1]

在cost[i-1][j+1]。在

没有第六元素。只有五个。因此IndexError。在

对于解决方案，如果您想要最后一个元素，您可能只想要n，而不是{}。不过，我不是百分之百肯定。在

Answer 3

为了避免索引器异常

if (j < n and cost[i-1][j+1] + p[i-1][j+1] > max):
  max = cost[i-1][j+1] + p[i-1][j+1]

应写：

^{pr2}$

以及

printsquares(w,i-1,w[i][j])

变成

printsquares(w,i-1,w[i-1][j])

但正如其他人所说，我不确定该算法是否正确实现。在