4/8 3.1 矩阵连乘

递归关系：

设计算A[i:j]，1≤i ≤j ≤n ，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]

当i=j 时，A[i:j]=Ai ，因此，m[i,i]=0，i=1,2,…,n

当i<j 时，j k i p p p j k m k i m j i m 1],1[],[],[-+++=，

可以递归地定义m[i,j]为：

⎪⎩⎪⎨⎧<+++==-<≤j i p p p j k m k i m j i j i m j k i }],1[],[{min 0],[1j

k i 掌握算法void MatrixChain (int *p ，int n ，int **m ，int **s)

掌握m[i,j]的计算方式和最优解的构造。

算法复杂度为O(n 3）

3.2 动态规划算法的基本要素

利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。

3.4 最大子段和

如果将所给的序列a[1:n]分为长度相等的2 段a[1:n/2]和a[n/2+1:n]，分别求出这2 段的最大子段和，则a[1:n]的最大子段和有3种情况：

(1) a[1:n]的最大子段和与a[1:n/2]最大子段和相同；

(2) a[1:n]的最大子段和与a[n/2+1:n]最大子段和相同； (3) a[1:n]的最大子段和为

, 且1≤i ≤n/2, n/2+1≤j ≤n 。

复杂度分析：

T(n)=O(nlogn)

掌握 maxSum(int n, int * a)

算法复杂度为O(n ）

3.10 0-1背包问题