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