动态规划 —— 最大子矩阵和

问题描述：

给你一个N*N的矩阵，要求找出其一个子矩阵，使其各元素之和为最大。
原题地址: POJ-1050 To the Max

算法分析：

1. 首先要学会最大子段和的求法(这道题的动态规划思想就体现在这里)
2. 利用求最大子段和的算法， 将二维动态规划问题转化为一维动态规划问题
   设一维数组b是二维数组a的i~j(0<=i<j<n)行，对应列元素的和，然后对数组b计算最大子段和。
3. 构造最优解

动态规划 —— 矩阵连乘积问题

问题描述：

给定n个矩阵{A1,A2,…,An}，其中Ai和Ai+1是可乘的，i=1，2…，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

算法分析：

问题的解空间：

n个矩阵可能的完全加括号方式有P(n)=Catalan(n-1)，所以P(n)是随n的指数级增长的，因此穷举法不是一个有效的算法。