動(dòng)態(tài)規(guī)劃與分治法的異同：

相同點(diǎn)：其基本思想都是將待求解問(wèn)題分解為若干子問(wèn)題，先求解子問(wèn)題，再結(jié)合這些子問(wèn)題的解得到原問(wèn)題的解。

差異點(diǎn)：與分治法不同的是，適合用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題經(jīng)分解得到的子問(wèn)題往往不是相互獨(dú)立的。有些問(wèn)題分解后的子問(wèn)題往往是重復(fù)的，此時(shí)若用分支法則會(huì)重復(fù)計(jì)算耗費(fèi)時(shí)間內(nèi)存。

總結(jié)：為了達(dá)到避免重復(fù)計(jì)算，可以用一個(gè)表來(lái)記錄所有已解決的子問(wèn)題的答案。不管該子問(wèn)題以后是否被用到，只要它被計(jì)算過(guò)，就將其結(jié)果填入表中。

步驟：

找出最優(yōu)解的性質(zhì)，刻畫(huà)其結(jié)構(gòu)特征。
遞歸地定義最優(yōu)值。
以自底向上的方式計(jì)算最優(yōu)值。
根據(jù)計(jì)算最優(yōu)值得到的信息構(gòu)造最優(yōu)解。
矩陣連乘問(wèn)題
分析最優(yōu)解的結(jié)構(gòu)
建立遞歸關(guān)系
計(jì)算最優(yōu)值
構(gòu)造最優(yōu)解
動(dòng)態(tài)規(guī)劃算法的基本要素

最優(yōu)子結(jié)構(gòu)：當(dāng)問(wèn)題的最優(yōu)解包含了其子問(wèn) 題的最優(yōu)解時(shí)，稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

重疊子問(wèn)題：在用遞歸算法自頂向下解此問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算。動(dòng)態(tài)規(guī)劃算法對(duì)每個(gè)子問(wèn)題只解一次，然后將解保存在一個(gè)表格中。

問(wèn)題描述：

給定n個(gè)矩陣：A1,A2,…,An，其中Ai與Ai+1是可乘的，i=1，2…，n-1。確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。輸入數(shù)據(jù)為矩陣個(gè)數(shù)和每個(gè)矩陣規(guī)模，輸出結(jié)果為計(jì)算矩陣連乘積的計(jì)算次序和最少數(shù)乘次數(shù)。

問(wèn)題解析：

由于矩陣乘法滿足結(jié)合律，故計(jì)算矩陣的連乘積可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來(lái)確定。若一

總結(jié)

以上是生活随笔為你收集整理的算法设计与分析——动态规划——矩阵连乘问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。