求个时间复杂度低的算法

teebye

题目：在国际象棋的棋盘上面有 NxN个格。每个格里面有若干的米粒。一只小猪站在1x1的格里，小猪每次只能向高位的列或行移动。小猪会吃掉所经过的格子里面所有的米粒。请编写程序计算小猪能吃掉的米粒的最大值，并得出最大值时小猪的路径。

我的代码

arr=[[2,2,3,0],[0,3,1,1],[1,2,2,1],[4,1,2,2]]

def max(a,b)
a,b = b,a if a<b
return a
end

def cal(arr)
r = arr[3][3]
i =3
j = 3
path="path: "+r.to_s+"->"
c = 0
while(i>0)
while(j>0)

c=max(arr[i-1][j],arr[j-1])
if c == arr[i-1][j]
i,j= i-1,j
else
i,j = i ,j-1
end
path << (c.to_s+"->")
r +=c
end
end
puts path
puts "max_value＝"+r.to_s

end
cal(arr)

打印结果：
path: 2->2->2->2->3->2->2->
max_value＝15

teebye

这个版面已经堕落了吗

DQP

longest path in dag

千年沉寂

代码：

#!/usr/bin/env python def value(lst):     i = j = 0;     for i in range(1,len(lst[0])):         lst[0][i]+=lst[0][i-1]     for i in range(1,len(lst)):         lst[i][0]+=lst[i-1][0]     for i in range(1,len(lst)):         for j in range(1,len(lst[0])):             lst[i][j] += max(lst[i-1][j],lst[i][j-1])     max_value = lst[i][j] #最大值     path = []  #逆向寻找最大值路径，path存储相应坐标     path.append((i+1,j+1))     while i > 1 and j>1:         if lst[i-1][j]>lst[i][j-1]:             i = i-1         else:             j = j-1         path.append((i+1,j+1))     if i > 1:         for x in range(i-1,-1,-1):             path.append((x+1,2))     elif j > 1:         for x in range(j-1,-1,-1):             path.append((2,x+1))     path.append((1,1))     print "Max Value: %d" % max_value     print "Path:",path[::-1] def main():     arr=[[2,2,3,0],[0,3,1,1],[1,2,2,1],[4,1,2,2]]     value(arr) if __name__ == '__main__':     main()

>>> Max Value: 15 Path: [(1, 1), (1, 2), (2, 2), (3, 2), (3, 3), (4, 3), (4, 4)]

动态规划，对于N*N的矩阵，时间复杂度为 O(N*N)

[ 本帖最后由 千年沉寂 于 2009-5-6 13:54 编辑 ]