如果沒有人告訴你矩陣連乘問題就應該用動態(tài)規(guī)劃的方法來解決，那么我們應該如何想到呢？
wiki：
動態(tài)規(guī)劃是這樣子的這里有對矩陣連乘問題的描述。首先應該對問題進行抽象，如果能夠了解問題中矩陣的部分，那么問題可以抽象成這樣
poj1651。這里問題的另一種簡單的表示方式就是：給定一列數(shù)，每次你可以從中抽取1個數(shù)（除去頭尾兩個數(shù)不可以抽取），設(shè)置一個score，當你抽取該數(shù)的時候，score要加上該數(shù)和左右兩個數(shù)的乘積，問抽取到最后只剩下頭尾兩個數(shù)的時候，怎樣的抽取順序可以使score的值最小呢？
很直觀的方法就是枚舉每種抽取方式，然后找出使score最小的那一次抽取。（這被稱為笨辦法）
先設(shè)有n個要抽取的數(shù)，也就是總數(shù)為n+2。我們試著從中抽取m個，那么我們會發(fā)現(xiàn)在省下的那些還沒被抽取的數(shù)字中應該存在一種抽取策略使得它們的score最小（
最優(yōu)子結(jié)構(gòu)，這里可以用簡單的反證法說明），換句話說，就是我們前面怎樣的抽取順序?qū)竺娌粫斐捎绊憽＿@里就說明了笨辦法為什么笨了：如果我們找出了后面抽取的最優(yōu)策略后，那么每次我們改變前面的m個數(shù)的抽取順序時，是不需要對后面抽取順序進行枚舉的，只有用最優(yōu)那個策略即可（
重疊子問題）。
那么這樣說的話，只要找出前面抽取的最優(yōu)策略和后面抽取的最優(yōu)策略的話，那么就可以找出這樣的結(jié)果：以先抽取m個為分界限的最優(yōu)解。那么要求抽取n個球的問題時，就需要從1開始到n/2為分界限的最優(yōu)解。然后再對每個子問題進行遞歸的求解，當n=1時那么問題無需再進行分解。
上面這樣子理解有個缺點：很難用計算機語言實現(xiàn)。問題在于先抽取m個數(shù)，這些數(shù)的位置不連續(xù)。其實把它改為連續(xù)的對題目的求解也是一樣的，不過這時候要找的就不是從1到n/2為分界限的最優(yōu)解了（這樣的話就不全面）。應該從開頭的1，一直到n-1進行找最優(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 }