㈠ 演算法 怎麼求矩陣鏈乘法的最優加全部括弧
給個思路 遞歸 把abcd拆成左右兩部分 有三種拆法 其實是n-1種 然後for 每一種 遞歸下去
㈡ 矩陣鏈乘法的O（nlogn）演算法
http://hi..com/_%E2d_%B7%B3_%DE%B2%C2%D2/blog/item/ae9ec050aadaed67853524a0.html
㈢ 矩陣鏈相乘問題 來個C#寫的或C/C++寫的
#include<stdio.h>
#include<stdlib.h>
#defineMAXN1000000
voidMatrix_Chain_Order(int*p,int*s,intN)
{
intn=N-1;
intm[N][N];
for(inti=1;i<=n;i++)
{
m[i][i]=0;
}
for(intl=2;l<=n;l++)/*lÊÇÁ´µÄ³¤¶È*/
{
for(inti=1;i<=n-l+1;i++)
{
intj=i+l-1;
m[i][j]=MAXN;
intq;
for(intk=i;k<=j-1;k++)
{
q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(q<m[i][j])
{
m[i][j]=q;
*(s+i*N+j)=k;
}
}
}
}
}
voidPrint_Optimal_Parens(int*s,inti,intj,intN)
{
if(i==j)
{
printf("A%d",i);
}
else
{
printf("(");
Print_Optimal_Parens((int*)s,i,*(s+i*N+j),N);
Print_Optimal_Parens((int*)s,*(s+i*N+j)+1,j,N);
printf(")");
}
}
intmain()
{
intP[7]={30,35,15,5,10,20,25};
intS[7][7];
Matrix_Chain_Order(P,(int*)S,7);
Print_Optimal_Parens((int*)S,1,6,7);
system("pause");
return0;
}
這是我以前實現矩陣鏈相乘的演算法，不符合你最終的顯示，你稍微改一下就好
㈣ 寫一篇《論演算法設計中的分治與增量》的學術論文1500字
一、動態規劃的基本思想
在比較基本的演算法設計思想里，動態規劃是比較難於理解，難於抽象的一種，但是卻又十分重要。動態規劃的實質是分治思想和解決冗餘，因此它與分治法和貪心法類似，它們都是將問題的實例分解為更小的、相似的子問題，但是動態規劃又有自己的特點。
貪心法的當前選擇可能要依賴於已經作出的選擇，但不依賴於還未做出的選擇和子問題，因此它的特徵是由頂向下，一步一步地做出貪心選擇，但不足的是，如果當前選擇可能要依賴子問題的解時，則難以通過局部的貪心策略達到全局最優解。相比而言，動態規劃則可以處理不具有貪心實質的問題。
在用分治法解決問題時，由於子問題的數目往往是問題規模的指數函數，因此對時間的消耗太大。動態規劃的思想在於，如果各個子問題不是獨立的，不同的子問題的個數只是多項式量級，如果我們能夠保存已經解決的子問題的答案，而在需要的時候再找出已求得的答案，這樣就可以避免大量的重復計算。由此而來的基本思路是，用一個表記錄所有已解決的子問題的答案，不管該問題以後是否被用到，只要它被計算過，就將其結果填入表中。
比較感性的說，其實動態規劃的思想是對貪心演算法和分治法的一種折衷，它所解決的問題往往不具有可愛的貪心實質，但是各個子問題又不是完全零散的，這時候我們用一定的空間來換取時間，就可以提高解題的效率。
二、動態規劃的基本步驟
動態規劃演算法通常用於求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應於一個值，我們希望找到具有最優值（最大值或最小值）的那個解。設計一個動態規劃演算法，通常可以按以下幾個步驟進行：
（1）找出最優解的性質，並刻畫其結構特徵。
（2）遞歸地定義最優值。
（3）以自底向上的方式計算出最優值。
（4）根據計算最優值時得到的信息，構造一個最優解。
其中（1）——（3）步是動態規劃演算法的基本步驟。在只需要求出最優值的情形，步驟（4）可以省去。若需要求出問題的一個最優解，則必須執行步驟（4）。此時，在步驟（3）中計算最優值時，通常需記錄更多的信息，以便在步驟（4）中，根據所記錄的信息，快速構造出一個最優解。
三、典型的動態規劃舉例——矩陣連乘問題
作為經典的動態規劃演算法舉例，矩陣連乘問題很好地展現了動態規劃的特點和實用價值。給定n個矩陣{A1,A2,...,An},其中Ai與Ai+1是可乘的，i=1,2,...n-1。現在要計算這n個矩陣的連乘積。由於矩陣的乘法滿足結合律，所以通過加括弧可以使得計算矩陣的連乘積有許多不同的計算次序。然而採用不同的加擴號方式，所需要的總計算量是不一樣的。若A是一個p*q矩陣，B是一個q*r矩陣，則其乘積C=AB是一個p*r矩陣。如果用標准演算法計算C，總共需要pqr次數乘。
現在來看一個例子。A1，A2，A3分別是10*100,100*5和5*50的矩陣。如果按照((A1A2)A3)來計算，則計算所需的總數乘次數是10*100*5+10*5*50=7500。如果按照(A1(A2A3))來計算，則需要的數乘次數是100*5*50+10*100*50=75000,整整是前者的10倍。由此可見，在計算矩陣連乘積時，不同的加括弧方式所導致的不同的計算對計算量有很大的影響。如何確定計算矩陣連乘積A1A2，...,An的一個計算次序，使得依此次序計算矩陣連乘積需要的數乘次數最少便成為一個問題。
對於這個問題，窮舉法雖然易於入手，但是經過計算，它所需要的計算次數是n的指數函數，因此在效率上顯得過於低下。現在我們按照動態規劃的基本步驟來分析解決這個問題，並比較它與窮舉法在時間消耗上的差異。
（1）分析最優解的結構。
現在，將矩陣連乘積AiAi+1...Aj簡記為A[i:j]。對於A[1:n]的一個最優次序，設這個計算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開(1<=k<n)，那麼完全加括弧的方式為((A1...Ak)(Ak+1...An))。依此次序，我們應該先分別計算A[1:k]和A[k+1:n]，然後將計算結果相乘得到A[1:n]，總計算量為A[1:k]的計算量加上A[k+1:n]的計算量，再加上A[1:k]和A[k+1:n]相乘的計算量。
通過反證法可以證明，問題的關鍵特徵在於，計算A[1:n]的一個最優次序所包含的計算矩陣子鏈A[1:k]和A[k+1:n]的次序也是最優的。因此，矩陣連乘積計算次序問題的最優解包含著其子問題的最優解。這種最優子結構性質是該問題可以用動態規劃解決的重要特徵。
（2）建立遞歸關系定義最優值。
設計算A[i:j](1<=i<=j<=n)所需的最少數乘次數為m[i][j]，則原問題的最優值為m[1][n]。而且易見，當i=j時，m[i][j]=0。
根據上述最優子結構性質，當i<j時，若計算A[i:j]的最優次序在Ak和Ak+1之間斷開，可以定義m[i][j]=m[i][k]+m[k+1][j]+pi-1*pk*pj(其中，Ai的維數為pi-1*pi)。從而有：
當i=j時，m[i][j]=0。
當i<j時，m[i][j]=min{m[i][k]+m[k+1][j]+pi-1*pk*pj} (i<=k<j)。
除此之外，若將對應於m[i][j]的斷開位置記為s[i][j]，在計算出最優值m[i][j]後，可以遞歸地由s[i][j]構造出相應的最優解。
（3）計算最優值。
如果直接套用m[i][j]的計算公式，進行簡單的遞歸計算需要耗費指數計算時間。然而，實際上不同的子問題的個數只是n的平方項級(對於1<=i<=j<=n不同的有序對(i,j)對應於不同的子問題)。用動態規劃解決此問題，可依據其遞歸式以自底向上的方式進行計算。在計算過程中，保存已解決的子問題答案。每個子問題只計算一次，而在後面需要時只要簡單查一下，從而避免大量的重復計算，最終得到多項式時間的演算法。下面給出計算m[i][j]的動態規劃演算法：
void matrixChain (int * p, int n, int * * m, int * * s)
{
for ( int i=1;i<=n;i++)
m[i][i]=0;
for ( int r=2;r<=n;r++) //鏈長度控制
for ( int i=1;i<=n-r+1;i++) //鏈起始位置控制
{
int j=i+r-1; //鏈終止位置
m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
s[i][j]=i;
for ( int k=i+1;k<j;k++)
{
int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if (t<m[i][j])
{
m[i][j]=t;
s[i][j]=k;
}
}
}
}
演算法首先設定m[i][i]=0(i=1,2,...,n)。然後再根據遞歸式按矩陣鏈長的遞增方式依此計算出各個m[i][j]，在計算某個固定的m[i][j]時，只用到已計算出的m[i][k]和m[k+1][j]。
稍加分析就可以得出，這個演算法以O(n^2)的空間消耗大大降低了時間復雜度，計算時間的上界為O(n^3)。
（4）構造最優解。
通過以上演算法的計算，我們知道了要計算所給矩陣連乘積所需的最少數乘次數，但是還不知道具體應該按照什麼順序來做矩陣乘法才能達到這個次數。然而，s[i][j]已經存儲了構造最優解所需要的足夠的信息。從s[1][n]記錄的信息可知計算A[1:n]的最優加括弧方式為(A[1:s[1][n]])(A[s[1][n]+1:n])。同理，每個部分的最優加括弧方式又可以根據數組s的相應元素得出。照此遞推下去，最終可以確定A[1:n]的最優完全加括弧方式，即構造出問題的一個最優解。
四、結語
本文簡單介紹了動態規劃的基本思想、步驟和簡單例題。以後筆者還會給大家介紹更多的例子，以及由動態歸劃衍生出來的備忘錄方法，使大家即使在不能清晰地分析出問題子結構的從屬關系時，仍能夠避免不必要的重復計算，快速地解決問題。
一、分治演算法
分治演算法的基本思想是將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。
分治法解題的一般步驟：
（1）分解，將要解決的問題劃分成若干規模較小的同類問題；
（2）求解，當子問題劃分得足夠小時，用較簡單的方法解決；
（3）合並，按原問題的要求，將子問題的解逐層合並構成原問題的解。
當我們求解某些問題時，由於這些問題要處理的數據相當多，或求解過程相當復雜，使得直接求解法在時間上相當長，或者根本無法直接求出。對於這類問題，我們往往先把它分解成幾個子問題，找到求出這幾個子問題的解法後，再找到合適的方法，把它們組合成求整個問題的解法。如果這些子問題還較大，難以解決，可以再把它們分成幾個更小的子問題，以此類推，直至可以直接求出解為止。這就是分治策略的基本思想。下面通過實例加以說明。
【例1】 [找出偽幣] 給你一個裝有1 6個硬幣的袋子。1 6個硬幣中有一個是偽造的，並且那個偽造的硬幣比真的硬幣要輕一些。你的任務是找出這個偽造的硬幣。為了幫助你完成這一任務，將提供一台可用來比較兩組硬幣重量的儀器，利用這台儀器，可以知道兩組硬幣的重量是否相同。比較硬幣1與硬幣2的重量。假如硬幣1比硬幣2輕，則硬幣1是偽造的；假如硬幣2比硬幣1輕，則硬幣2是偽造的。這樣就完成了任務。假如兩硬幣重量相等，則比較硬幣3和硬幣4。同樣，假如有一個硬幣輕一些，則尋找偽幣的任務完成。假如兩硬幣重量相等，則繼續比較硬幣5和硬幣6。按照這種方式，可以最多通過8次比較來判斷偽幣的存在並找出這一偽幣。
另外一種方法就是利用分而治之方法。假如把1 6硬幣的例子看成一個大的問題。第一步，把這一問題分成兩個小問題。隨機選擇8個硬幣作為第一組稱為A組，剩下的8個硬幣作為第二組稱為B組。這樣，就把1 6個硬幣的問題分成兩個8硬幣的問題來解決。第二步，判斷A和B組中是否有偽幣。可以利用儀器來比較A組硬幣和B組硬幣的重量。假如兩組硬幣重量相等，則可以判斷偽幣不存在。假如兩組硬幣重量不相等，則存在偽幣，並且可以判斷它位於較輕的那一組硬幣中。最後，在第三步中，用第二步的結果得出原先1 6個硬幣問題的答案。若僅僅判斷硬幣是否存在，則第三步非常簡單。無論A組還是B組中有偽幣，都可以推斷這1 6個硬幣中存在偽幣。因此，僅僅通過一次重量的比較，就可以判斷偽幣是否存在。
現在假設需要識別出這一偽幣。把兩個或三個硬幣的情況作為不可再分的小問題。注意如果只有一個硬幣，那麼不能判斷出它是否就是偽幣。在一個小問題中，通過將一個硬幣分別與其他兩個硬幣比較，最多比較兩次就可以找到偽幣。這樣，1 6硬幣的問題就被分為兩個8硬幣（A組和B組）的問題。通過比較這兩組硬幣的重量，可以判斷偽幣是否存在。如果沒有偽幣，則演算法終止。否則，繼續劃分這兩組硬幣來尋找偽幣。假設B是輕的那一組，因此再把它分成兩組，每組有4個硬幣。稱其中一組為B1，另一組為B2。比較這兩組，肯定有一組輕一些。如果B1輕，則偽幣在B1中，再將B1又分成兩組，每組有兩個硬幣，稱其中一組為B1a，另一組為B1b。比較這兩組，可以得到一個較輕的組。由於這個組只有兩個硬幣，因此不必再細分。比較組中兩個硬幣的重量，可以立即知道哪一個硬幣輕一些。較輕的硬幣就是所要找的偽幣。
【例2】在n個元素中找出最大元素和最小元素。我們可以把這n個元素放在一個數組中，用直接比較法求出。演算法如下：
void maxmin1(int A[],int n,int *max,int *min)
{ int i;
*min=*max=A[0];
for(i=2;i < n;i++)
{ if(A > *max) *max= A;
if(A < *min) *min= A;
}
}
上面這個演算法需比較2(n-1)次。能否找到更好的演算法呢？我們用分治策略來討論。
把n個元素分成兩組：
A1={A[1],...,A[int(n/2)]}和A2={A[INT(N/2)+1],...,A[N]}
分別求這兩組的最大值和最小值，然後分別將這兩組的最大值和最小值相比較，求出全部元素的最大值和最小值。如果A1和A2中的元素多於兩個，則再用上述方法各分為兩個子集。直至子集中元素至多兩個元素為止。
例如有下面一組元素：-13，13，9，-5，7，23，0，15。用分治策略比較的過程如下：
圖中每個方框中，左邊是最小值，右邊是最大值。從圖中看出，用這種方法一共比較了10次，比直接比較法的14次減少4次，即約減少了1/3。演算法如下：
void maxmin2(int A[],int i,int j,int *max,int *min)
/*A存放輸入的數據，i，j存放數據的范圍，初值為0，n-1，*max,int *min 存放最大和最小值*/
{ int mid,max1,max2,min1,min2;
if (j==i) {最大和最小值為同一個數;return;}
if (j-1==i) {將兩個數直接比較，求得最大會最小值；return；}
mid=(i+j)/2;
求i~mid之間的最大最小值分別為max1，min1;
求mid+1~j之間的最大最小值分別為max2，min2;
比較max1和max2，大的就是最大值;
比較min1和min2，小的就是最小值;
}
利用分治策略求解時，所需時間取決於分解後子問題的個數、子問題的規模大小等因素，而二分法，由於其劃分的簡單和均勻的特點，是經常採用的一種有效的方法，例如二分法檢索。運用分治策略解決的問題一般來說具有以下特點：
1、原問題可以分解為多個子問題，這些子問題與原問題相比，只是問題的規模有所降低，其結構和求解方法與原問題相同或相似。
2、原問題在分解過程中，遞歸地求解子問題，由於遞歸都必須有一個終止條件，因此，當分解後的子問題規模足夠小時，應能夠直接求解。
3、在求解並得到各個子問題的解後，應能夠採用某種方式、方法合並或構造出原問題的解。
不難發現，在分治策略中，由於子問題與原問題在結構和解法是的相似性，用分治方法解決的問題，大都採用了遞歸的形式。在各種排序方法中，如歸並排序、堆排序、快速排序等，都存在有分治的思想。
㈤ 考慮將MATCHAIN演算法應用於下述5個矩陣鏈相乘的問題：
不會做哦！我的40分都沒有人回答！
㈥ 動態規劃如何去找動態轉移方程
1、最長公共子串
假設兩個字元串為str1和str2，它們的長度分別為n和m。d[i][j]表示str1中前i個字元與str2中前j個字元分別組成的兩個前綴字元串的最長公共長度。這樣就把長度為n的str1和長度為m的str2劃分成長度為i和長度為j的子問題進行求解。狀態轉移方程如下：
dp[0][j] = 0; (0<=j<=m)
dp[i][0] = 0; (0<=i<=n)
dp[i][j] = dp[i-1][j-1] +1; (str1[i] == str2[j])
dp[i][j] = 0; (str1[i] != str2[j])
因為最長公共子串要求必須在原串中是連續的，所以一但某處出現不匹配的情況，此處的值就重置為0。
詳細代碼請看最長公共子串。
2、最長公共子序列
區分一下，最長公共子序列不同於最長公共子串，序列是保持子序列字元串的下標在str1和str2中的下標順序是遞增的，該字元串在原串中並不一定是連續的。同樣的我們可以假設dp[i][j]表示為字元串str1的前i個字元和字元串str2的前j個字元的最長公共子序列的長度。狀態轉移方程如下：
dp[0][j] = 0; (0<=j<=m)
dp[i][0] = 0; (0<=i<=n)
dp[i][j] = dp[i-1][j-1] +1; (str1[i-1] == str2[j-1])
dp[i][j] = max{dp[i][j-1],dp[i-1][j]}; (str1[i-1] != str2[j-1])
詳細代碼請看最長公共子序列。
3、最長遞增子序列（最長遞減子序列）
因為兩者的思路都是一樣的，所以只給出最長遞減子序列的狀態轉移方程。假設有序列{a1,a2,...,an}，我們求其最長遞增子序列長度。按照遞推求解的思想，我們用F[i]代表若遞增子序列以ai結束時它的最長長度。當 i 較小，我們容易直接得出其值，如 F[1] = 1。那麼，如何由已經求得的 F[i]值推得後面的值呢？假設，F[1]到F[x-1]的值都已經確定，注意到，以ax 結尾的遞增子序列，除了長度為1的情況，其它情況中，ax都是緊跟在一個由 ai(i < x)組成遞增子序列之後。要求以ax結尾的最長遞增子序列長度，我們依次比較 ax 與其之前所有的 ai(i < x)， 若ai小於 ax，則說明ax可以跟在以ai結尾的遞增子序列之後，形成一個新的遞 增子序列。又因為以ai結尾的遞增子序列最長長度已經求得，那麼在這種情況下，由以 ai 結尾的最長遞增子序列再加上 ax 得到的新的序列，其長度也可以確定，取所有這些長度的最大值，我們即能得到 F[x]的值。特殊的，當沒有ai(i < x)小 於ax， 那麼以 ax 結尾的遞增子序列最長長度為1。 即F[x] = max{1,F[i]+1|ai<ax && i<x}。
詳細代碼請看最長遞增子序列。
4、最大子序列和的問題
假設有序列{a1,a2,...,an}，求子序列的和最大問題，我們用dp[i]表示以ai結尾的子序列的最大和。
dp[1] = a1; (a1>=0 && i == 1)
dp[i] = dp[i-1]+ai; (ai>=0 && i>=2)
dp[i] = 0; (dp[i-1] + ai <=0 && i>=2)
詳細代碼請看最大子序列的和。
5、數塔問題（動態搜索）
給定一個數組data[n][m]構成一個數塔求從最上面走到最低端經過的路徑和最大。可以假設dp[i][j]表示走到第i行第j列位置處的最大值，那麼可以推出狀態轉移方程：
dp[i][j] = max{dp[i-1][j-1],dp[i-1][j]} + data[i][j];
View Code
6、（01）背包問題
這是一個經典的動態規劃問題，另外在貪心演算法里也有背包問題，至於二者的區別在此就不做介紹了。
假設有N件物品和一個容量為V的背包。第i件物品的體積是v[i]，價值是c[i]，將哪些物品裝入背包可使價值總和最大？
每一種物品都有兩種可能即放入背包或者不放入背包。可以用dp[i][j]表示第i件物品放入容量為j的背包所得的最大價值，則狀態轉移方程可以推出如下：
dp[i][j]=max{dp[i-1][j-v[i]]+c[i],dp[i-1][j]};
View Code
可以參照動態規劃 - 0-1背包問題的演算法優化、動態規劃-完全背包問題、動態規劃-多重背包問題
7、矩陣連乘（矩陣鏈問題）-參考《演算法導論》
例如矩陣鏈<A1,A2,A3>,它們的維數分別為10*100,100*5,5*50，那麼如果順序相乘即((A1A2)A3)，共需10*100*5 + 10*5*50 = 7500次乘法，如果按照(A1(A2A3))順序相乘，卻需做100*5*50 + 10*100*50 = 75000次乘法。兩者之間相差了10倍，所以說矩陣鏈的相乘順序也決定了計算量的大小。
我們用利用動態規劃的方式(dp[i][j]表示第i個矩陣至第j個矩陣這段的最優解,還有對於兩個矩陣A(i,j)*B(j,k)則需要i*j*k次乘法)，推出狀態轉移方程：
dp[i][j] = 0; (i ==j，表示只有一個矩陣，計算次數為0)
dp[i][j] = min{dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]}; (i<j && i<=k<j)
dp[1][n]即為最終求解.
View Code
㈦ （150分）懂C++動態規劃的進
理解動態規劃中矩陣鏈乘的狀態表示的具體含義，和遞歸定義，才有助於理解問題。
p應該是指向一個一個維數組的首地址，表示矩陣的維數。例如：矩陣鏈
A1,A2,A3,Ai,...,An;其中i=1,2,...,n;它的維數表示為
pi-1,pi.但是由於Ai的列和Ai+1的行數是一樣的。
所以矩陣鏈表示成維數後就為：
p0,p1,p2,p3,...,pn;
而p指向的就是存儲p0,p1,p2,p3,...,pn;的數組首地址。
n表示數組元素個數。
m它用來指向m[][]的首地址，它是用來存儲一個最優值。
m[i][j]為計算矩陣鏈中Ai到Aj的乘法運算次數的最小值。
也就是最優子結構的狀態值。
下面你要理解這個狀態的遞歸定義。
對於m[i][j]來說，如果i=j.則鏈中只有一個矩陣，不需要乘法。所以
m[i][i]=0;也就是你程序中
for (int i = 1; i <= n; i++) m[i][i] = 0;
但是如果i<j的時候，假設通過加括弧將乘積AiAi+1...Aj,從Ak和Ak+1之間分開，其中k為i到j;因此計算乘積AiAi+1...Aj最小運算次數等於計算
Ai...Ak和計算Ak+1...Aj的這兩個最小運算次數加上計算上述Ai...Ak和Ak+1...Aj這兩個矩陣相乘的次數。其中i=<k<j;取其中的最小值。
這也就是你程序中
for (int k = i+1; k < j; k++) {
int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if (t < m[i][j]) { m[i][j] = t; s[i][j] = k;}
}
但是你注意到它的k是從i+1開始的，不是i和上面說的不一樣。
這是因為在程序設計的時候，它首先在外面把k=i的時候計算出來了直接放到了
m[i][j]作為一個標兵，以後在計算後面k值取最小的時候，就和它直接比較取最小值就可以了。也就是程序中
if (t < m[i][j]) { m[i][j] = t; s[i][j] = k;}
這時候你注意s[i][j]=k.
這就說明了它是用來保存一個子狀態中k取什麼值的時候m[i][j]最優。
舉個例子，例如：
m[3][8]=500,s[3][8]=5.表示矩陣鏈A3...A8乘積的時候，從A5出分開計算得到最優解。
上面的是狀態表示和遞歸。
for (int r = 2; r <= n; r++)
也就是r它是為了實現從底向上遞推求出m[i][j]用來手段。
r表示步長。
表示m[i][j]中有幾個矩陣相乘。
因為初始的時候，一個矩陣的時候m[i][i]=0;
for (int i = 1; i <= n; i++) m[i][i] = 0;
所以它就根據遞歸中k的取值
從m[i][j]中為2個矩陣到n個矩陣依次計算，求得最優解。注意n個矩陣的時候，就是我們要的值。
說的這么多，不知道對你有幫助沒，
不明白的話，可以hi我，如果我在線的話。
㈧ 用動態規劃解決矩陣鏈乘法問題時，最優子結構問題是什麼
1、兩種重要演算法思想： 動態規劃，貪心演算法
2、動態規劃：
基本原理：動態規劃英文名dynamic programming。其中pogramming指的是表格法，而非編寫計算機程序。因此，可以初步得出動態規劃的基本思想：將一個具有最優子結構性質的問題分成若干個子問題，在求解過程中，記錄下子問題的結果，存儲在一個表格中，使得公共的子問題只需要計算一次。書中給出的基本原理：動態規劃將問題分成若干個相互重疊的子問題，遞歸的求解子問題，保存子問題的解，再將它們的解組合起來，求出原問題的解。
從基本原理中可以看出動態規劃需要滿足兩個條件，最優子結構和子問題重疊。
最優子結構：書中定義：問題的最優解由相關子問題的最優解組合而成，一個問題的最優解包含其子問題的最優解。典型的有背包問題和鋼條切割我問題。所謂子問題就是一中組合，將一個問題分成許多子問題的集合。某個子問題轉化為問題時，所需要的代價是固定的。
一般這類問題的解題過程：（自己總結）
畫出子問題圖（類似於逆拓撲排序的圖，子問題必須在問題前面完成）
用數學表達式構建出問題的最優解和子問題最優解之間的代數表達式
通常採用自底向上的方法進行遞歸地求解問題的解，自底下上的含義是從最小的子問題求起。
保存每一步求出的子問題的最優解
利用計算出的信息構造一個最優解
3、貪心演算法：
基本原理：從初始狀態出發，每步都經過貪心選擇，最終得到問題的最優解。
含義： 將每一步都看成是當前最佳的選擇，做到局部最優化，直到無法選擇為止。寄希望於局部最優的選擇能夠導致全局最優解。
兩個實例：最小生成樹演算法和單源最短路徑演算法，以及集合覆蓋問題的貪心啟發式演算法。
prim演算法：將集合A看成是一棵樹，每次選擇剩餘的節點中與這棵樹形成的邊的權值最小的點加入到集合A中形成新的樹，循壞調用該過程，知道所有的點都已經放入到集合A中。初始時隨機選擇一個節點放入到集合A中。
kruskal演算法：在所有連接森林中兩顆不同樹的邊裡面，找到權重最小的邊（u，v），並將其加入到集合A中，循環調用該過程，直到所有的點已經放入到集合A中
貪心選擇：當進行選擇時，我們直接作在當前問題看來是最優的選擇，而不必考慮子問題的解。這與動態規劃不同，動態規劃當前問題依賴於較小的子問題。而貪心演算法中做當前問題最優選擇，這樣每步之後只需要做一個子問題的解。
也必須滿足最優子結構的性質，即一個問題的最優解包含其子問題的最優解。
那麼，如何區分什麼時候使用動態規劃，什麼時候使用貪心演算法呢？
典型的兩個問題，0-1背包和分數背包。兩者都具有最優子結構性質，但是貪心演算法只能用來求分數背包的問題，而不能用來求0-1背包的問題。即只有分數背包具有貪心選擇性。
我得總結（不一定對）：具有貪心選擇性的一類問題是：每次做選擇時只有性能不同，而代價是一樣的。那麼這樣每次的選擇都是最好的，最終會得到最好的結果。
哈夫曼編碼也使用貪心選擇演算法。每次選擇待編碼的字元都選擇在剩餘的字元中出現次數最多的