Chinaunix

标题: 求个时间复杂度低的算法 [打印本页]
作者: teebye    时间: 2009-05-06 09:34
标题: 求个时间复杂度低的算法
题目：在国际象棋的棋盘上面有 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    时间: 2009-05-06 10:16
这个版面已经堕落了吗
作者: DQP    时间: 2009-05-06 10:27
longest path in dag
作者: 千年沉寂    时间: 2009-05-06 13:53
代码：
#!/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 编辑 ]



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2