動(dòng)態(tài)規(guī)劃算法與分治法類似平夜，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題 腰鬼，但是適合于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題經(jīng)分解得到的子問(wèn)題 往往不是互相獨(dú)立的嵌赠。如果能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案熄赡，就可以避免大量重復(fù)計(jì)算姜挺，本質(zhì)上是犧牲空間效率換取時(shí)間效率。
矩陣連乘問(wèn)題：找到最佳乘法運(yùn)算次序彼硫，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少
例如 需要的數(shù)乘次數(shù)為
炊豪，代碼表示如下：
def matrix_mul(A,B): # 時(shí)間復(fù)雜度 n1 * n2 *n3
n1=A.shape[0]
n2=A.shape[1]
n3=B.shape[1]
C=np.zeros([n1,n3])
for i in range(n1):
for j in range(n3):
for k in range(n2):
C[i][j] = C[i][j] +A[i][k]*B[k][j]
return C
動(dòng)態(tài)規(guī)劃算法思想
第一次最佳分割點(diǎn)：假設(shè)找到了矩陣連乘鏈的最佳運(yùn)算次序，（實(shí)際就是一個(gè)添加括號(hào)的過(guò)程）拧篮，使得矩陣鏈第一次在處斷開(kāi)词渤，即
則總計(jì)算量= 的計(jì)算量 +
的計(jì)算量 +
和
相乘的計(jì)算量，從該等式不難看出問(wèn)題具有最有子結(jié)構(gòu)性質(zhì)（即一個(gè)問(wèn)題的最優(yōu)解一定包含其子問(wèn)題的最優(yōu)解串绩，可以通過(guò)反證法證明）缺虐，于是可以不斷地進(jìn)行遞歸求解： 通過(guò)自底向上進(jìn)行遍歷長(zhǎng)度為L(zhǎng)的矩陣鏈，得到任意子問(wèn)題
的最優(yōu)解礁凡，保存起來(lái)高氮，以求得父問(wèn)題的最優(yōu)解慧妄。
相關(guān)定義：
定義存儲(chǔ)矩陣維度的列表dim ：dim[n+1]=[d1,d2,d3, ... ,dn+1] 其中矩陣的維度為
。
任意矩陣鏈的計(jì)算量纫溃，用
cost[i][j]表示
任意矩陣鏈的第一次最佳分割點(diǎn)腰涧，用
split[i][j] 表示
主要python代碼：
代碼思路：遍歷長(zhǎng)度為lenth的矩陣鏈，同時(shí)遍歷首次最佳分割點(diǎn)k, 不斷更新cost[i][j]紊浩、split[i][j]的值。
#自下而上
def matrix_chains_dp(dim,n,cost,split):
# dim : d1,d2,d3,... dn+1
# spit：記錄矩陣鏈的第一次最佳分割點(diǎn) ,計(jì)數(shù)下標(biāo)從1開(kāi)始
for i in range(1,n+1):
cost[i][i]=0
split[i][i]=-1 #矩陣鏈長(zhǎng)度為1時(shí)疗锐，沒(méi)有分割點(diǎn)
for lenth in range(2,n+1): #遍歷矩陣鏈條的長(zhǎng)度
#遍歷所有可能的 長(zhǎng)度為lenth的矩陣乘法鏈
for i in range (1,n-lenth+1+1):
j=i+lenth-1 #A[i:j] 表示矩陣乘法鏈條 Ai...Aj
for k in range(i,j): # 遍歷所有可能的分割點(diǎn): from i to j-1
cost_new=cost[i][k] + cost[k+1][j] +dim[i]*dim[k+1]*dim[j+1]
if(cost_new < cost[i][j]): #更新cost 以及分割點(diǎn) k
cost[i][j] = cost_new
split[i][j] = k
return cost,split
# 時(shí)間復(fù)雜度：O(n^3)
# 空間復(fù)雜度：O(n^2) 兩個(gè)二維數(shù)組
測(cè)試代碼
dim=[0,30,35,15,5,10,20,25] #計(jì)數(shù)從1開(kāi)始坊谁，用0填充一位
c=99999*np.ones([7,7])
s=np.zeros([7,7])
n=6
cost,split=matrix_chains_dp(dim,n,c,s)
print(cost,'\n',split)
