如果沒有人告訴你矩陣連乘問題就應(yīng)該用動態(tài)規(guī)劃的方法來解決，那么我們應(yīng)該如何想到呢？
wiki：
動態(tài)規(guī)劃是這樣子的這里有對矩陣連乘問題的描述。首先應(yīng)該對問題進(jìn)行抽象，如果能夠了解問題中矩陣的部分，那么問題可以抽象成這樣
poj1651。這里問題的另一種簡單的表示方式就是：給定一列數(shù)，每次你可以從中抽取1個(gè)數(shù)（除去頭尾兩個(gè)數(shù)不可以抽?。O(shè)置一個(gè)score，當(dāng)你抽取該數(shù)的時(shí)候，score要加上該數(shù)和左右兩個(gè)數(shù)的乘積，問抽取到最后只剩下頭尾兩個(gè)數(shù)的時(shí)候，怎樣的抽取順序可以使score的值最小呢？
很直觀的方法就是枚舉每種抽取方式，然后找出使score最小的那一次抽取。（這被稱為笨辦法）
先設(shè)有n個(gè)要抽取的數(shù)，也就是總數(shù)為n+2。我們試著從中抽取m個(gè)，那么我們會發(fā)現(xiàn)在省下的那些還沒被抽取的數(shù)字中應(yīng)該存在一種抽取策略使得它們的score最?。?strong>最優(yōu)子結(jié)構(gòu)，這里可以用簡單的反證法說明），換句話說，就是我們前面怎樣的抽取順序?qū)竺娌粫斐捎绊憽＿@里就說明了笨辦法為什么笨了：如果我們找出了后面抽取的最優(yōu)策略后，那么每次我們改變前面的m個(gè)數(shù)的抽取順序時(shí)，是不需要對后面抽取順序進(jìn)行枚舉的，只有用最優(yōu)那個(gè)策略即可（
重疊子問題）。
那么這樣說的話，只要找出前面抽取的最優(yōu)策略和后面抽取的最優(yōu)策略的話，那么就可以找出這樣的結(jié)果：以先抽取m個(gè)為分界限的最優(yōu)解。那么要求抽取n個(gè)球的問題時(shí)，就需要從1開始到n/2為分界限的最優(yōu)解。然后再對每個(gè)子問題進(jìn)行遞歸的求解，當(dāng)n=1時(shí)那么問題無需再進(jìn)行分解。
上面這樣子理解有個(gè)缺點(diǎn)：很難用計(jì)算機(jī)語言實(shí)現(xiàn)。問題在于先抽取m個(gè)數(shù)，這些數(shù)的位置不連續(xù)。其實(shí)把它改為連續(xù)的對題目的求解也是一樣的，不過這時(shí)候要找的就不是從1到n/2為分界限的最優(yōu)解了（這樣的話就不全面）。應(yīng)該從開頭的1，一直到n-1進(jìn)行找最優(yōu)解。
這是poj1651的代碼：
1 #include<iostream>
2 using namespace std;
3 const int inf = 0xffffff;
4 int dp[101][101];
5 int num[101];
6 void input(int n){
7 for(int i = 1 ; i <= n; i++)
8 cin>>num[i];
9 for(int i = 0; i <= n; i++)
10 for(int j = 0 ; j <= n; j++)
11 dp[i][j] = inf;
12 }
13 int solve(int a,int b){
14 if(dp[a][b] != inf)return dp[a][b];
15 if(b - a == 2){
16 dp[a][b] = num[a]*num[a+1]*num[b];
17 return dp[a][b];
18 }
19 if(b - a == 1){
20 dp[a][b] = 0;
21 return dp[a][b];
22 }
23 int min = inf;
24 int temp;
25 for(int i = a+1 ; i < b; i ++){
26 temp = solve(a,i) + solve(i,b) + num[a]*num[i]*num[b];
27 if(temp < min) min = temp;
28 }
29 dp[a][b] = min;
30 return dp[a][b];
31 }
32 int main(){
33 int n;
34 while(cin >> n){
35 input(n);
36 cout << solve(1,n)<<endl;
37 }
38 }