key_probability = [-1, 0.15, 0.1, 0.05, 0.1, 0.2]
virtual_key_probability = [0.05, 0.1, 0.05, 0.05, 0.05, 0.1]
expect_cost = [[0] *10 for i in range(10)]
probability_sum = [[0] *10 for i in range(10)]
root = [[0] *10 for i in range(10)]
def optimal_bst():
global expect_cost
global probability_sum
for i in range(1, 6):
expect_cost[i][i-1] = virtual_key_probability[i-1]
probability_sum[i][i-1] = virtual_key_probability[i-1]
for step in range(0, 5):
for i in range(1, 6):
this_time_end = i + step
if this_time_end > 5:
break
probability_sum[i][this_time_end] = probability_sum[i][this_time_end-1] + key_probability[this_time_end] + virtual_key_probability[this_time_end]
# print i,this_time_end, probability_sum[i][this_time_end]
print "item", expect_cost[i][i-1], expect_cost[i+1][this_time_end], probability_sum[i][this_time_end]
print "value", expect_cost[i][i-1]+expect_cost[i+1][this_time_end]+probability_sum[i][this_time_end]
expect_cost_min = expect_cost[i][i-1] + expect_cost[i+1][this_time_end] + probability_sum[i][this_time_end]
print "expect", expect_cost_min
root[i][this_time_end] = i
# print i, this_time_end, expect_cost_min
for j in range(i, this_time_end+1):
cur_cost = expect_cost[i][j-1] + expect_cost[j+1][this_time_end] + probability_sum[i][this_time_end]
if cur_cost < expect_cost_min:
expect_cost_min = cur_cost
root[i][this_time_end] =j
expect_cost[i][this_time_end] = expect_cost_min
# print i, this_time_end, expect_cost[i][this_time_end]
def find_root(begin,end,r):
if begin >= end:
return
k = root[begin][end]
print begin, end, k
find_root(begin,k-1,r)
find_root(k+1,end,r)
optimal_bst()
# find_root(1,5)
for i in range(1,6):
print root[i]
# print root
print "value",expect_cost[1][5]
Dynamic programming--optimal binary search tree
原文：http://www.cnblogs.com/zhaodonglin/p/5564796.html