python - 棋盘算法实现

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

你非常想这样做：

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

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

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

至于解决方案，您可能只想要n而不是n+1如果您想要最后一个元素。但是，我不能 100% 确定。

Answer 2

看起来您正在尝试从列表从 1 开始而在 Python 中从 0 开始的语言改编算法。据我检查，您永远不会访问cost[i][0].

Answer 3

为了避免 IndexError 异常，

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]

应该写成：

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

和

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

变成

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

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