文档介绍：算法总体思想
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级在用分治法求解时，有些子问题被重复计算了许多次。
如果能够保存已解决的子问题;
if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}
}
}
}
m[2][5]二
m[2][2]+m[3][5]+ppp
125
min〈m[2][3]+m[4][5]+ppp
135
二0+2500+35x15x20二13000
二2625+1000+35x5x20二7125
二4375+0+35x10x20二11375
A1
A2J
A3
A4
A5
A6
30x3
35x1
15x
5x1
10x2
20x25
m[2][4]+m[5][5]+ppp
145
算法复杂度分析：
算法matrixchain的主要计算量取决于算法中对r,i和k的3重循环。循环体内的计算量为
0(1),而3重循环的总次数为0伸)。因此算法的计算时间上界为0伸)。算法所占用的空间显然为O(n2)。
123456
12
3
4
5
6
L
2
S4
56
L10167K)
7S75
9375
11875
15126
iiJ
13
3
3
30
3S25
4375
7125
10500
2
0
23
3
3
-.：■■■
呂
750
2ECC
5375
3
03
3
3
1OTJ
□5M
J
■'
4
=；
E
0
SOUCi
E.
i
5
6
0
官
0
.＜计埠初序
-'I'1
卍fTl
动态规划算法的基本要素
一、最优子结构
矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
在分析问题的最优子结构性质时,所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的,然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用
小，问题的维度低）二、重叠子问题
•递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
•动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次
需要解此子问题时，只是简单地用常数时间查看一下结果。
•通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。
22231：122334洱1：1胡1况妲
三、备忘录方法
•备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。
intLookupChain(inti，intj)
{
if(m[i][j]>0)returnm[i][j];
if(i==j)return0;
intu=LookupChain(i，i)+LookupChain(i+1，j)+p[i-1]*p[i]*p[j];
s[i][j]=i;
for(intk=i+1;k<j;k++){
intt=LookupChain(i，k)+LookupChain(k+1，j)+p[i-1]*p[k]*p[j];
if(t<u){u=t;s[i][j]=k;}
}
m[i][j]=u;
returnu;
最长公共子序列
・若给定序列'K={xi,x2,^,x}，则另一序列乙=亿忆2,...%}，是X的子序列是指存在一个严12m12k
格递增下标序列{i1,i2,.,ik}使得对于所有j=12・..,k有：兮乂口。例如，序列
Z={B,C,D,
B}是序列X={A,B，C，B，D，A，B}的子序列，相应的递增下标序列为{2,3,5,7}。
给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
给定2个序列X={xi7x2，.,xm}和Y={yi7y2，.,yn}，找出X和Y的最长公共子序列。
设序列X={xi7x2,.,xm}和Y={yi7y2,.,yn}的最长公共子序列为乙也必,..％}