p=[0,8,7,4,2,5,1,9,3,10,6]
size= [[0 for col in range(0,11)] for row in range(0,11)]
def calc_max_num():
for j in range(1,11):
if (j >= p[0]):
size[1][j] = 1
else:
size[1][j] = 0
for i in range(1,11):
for j in range(1,p[i]):
size[i][j] = size[i-1][j]
for j in range(p[i],11):
size[i][j] = max(size[i-1][p[i]-1]+1, size[i-1][j])
def get_cur_lines(size, i,j):
while (size[i][j]!=0):
if (size[i][j] != size[i-1][j]):
print i,p[i]
j = p[i]-1
i = i-1
else:
i = i-1
j =j
calc_max_num()
print size[10][10]
get_cur_lines(size,10,10)
Dynamic programming--circuit board
原文：http://www.cnblogs.com/zhaodonglin/p/5524660.html