polygon_vertex=[5,-7,4,2]
polygon_side=[‘+‘,‘+‘,‘*‘,‘*‘]
multi_list = [[[0 for col in range(5)] for row in range(5)] for i in range(5)]
def get_min_of_four(val_1, val_2, val_3, val_4):
minium = val_1
if minium> val_2:
minium = val_2
if minium > val_3:
minium = val_3
if minium > val_4:
minium = val_4
return minium
def get_max_of_four(val_1, val_2, val_3, val_4):
maximum = val_1
if maximum < val_2:
maximum = val_2
if maximum < val_3:
maximum = val_3
if maximum < val_4:
maximum = val_4
return maximum
def get_min_and_max(multi_list, vertex, split, length):
first_seg_min = multi_list[vertex][split][0]
first_seg_max = multi_list[vertex][split][1]
second_seg_vertex = (vertex+split)%4
second_seg_min = multi_list[second_seg_vertex][length-split][0]
second_seg_max = multi_list[second_seg_vertex][length-split][1]
index = (vertex+split-1)%4
oper = polygon_side[index]
if oper == ‘+‘:
return first_seg_min+ second_seg_min, first_seg_max + second_seg_max
else:
val_1 = first_seg_min * second_seg_min
val_2 = first_seg_min * second_seg_max
val_3 = first_seg_max * second_seg_min
val_4 = first_seg_max * second_seg_max
return get_min_of_four(val_1, val_2, val_3, val_4), get_max_of_four(val_1, val_2, val_3, val_4)
def calc_max_val(multi_list):
for i in range(0,4):
multi_list[i][1][0] = polygon_vertex[i]
multi_list[i][1][1] = polygon_vertex[i]
for length in range(2,5):
for vertex in range(0,4):
minimum, maximum = get_min_and_max(multi_list, vertex, 1, length)
for split in range(2,length):
cur_minimum, cur_maximum = get_min_and_max(multi_list, vertex, split, length)
if cur_minimum < minimum:
minimum = cur_minimum
if cur_maximum > maximum:
maximum = cur_maximum
multi_list[vertex][length][0] = minimum
multi_list[vertex][length][1] = maximum
print vertex, minimum, maximum, length
calc_max_val(multi_list)
def get_maximum(multi_list):
max_index=0
maximum = multi_list[0][4][1]
for i in range(0,4):
# maximum = multi_list[i][4][1]
print i, multi_list[i][4][1]
if multi_list[i][4][1] > maximum:
maximum = multi_list[i][4][1]
max_index = i
return maximum, max_index
print get_maximum(multi_list)
Dynamic programming-polygon game
原文：http://www.cnblogs.com/zhaodonglin/p/5502768.html