解决动态规划问题的关键：找状态，描述状态转移方程 难点：怎么分阶段，怎么找状态 今天讲了动态规划的第二组例题，这一组的题目要比上周讲的复杂，理解起来难度也更大，整个问题的维度从一维上升到了二维。因此解决问题就有了相应的对策，将二维降阶，每一个子问题就是一个一维的动态规划了，这样问题就方便求解了。 1.最大子矩阵 给定N和一个NN得矩阵，求该矩阵的一个子矩阵，使子矩阵中所有数字的和最大，求出这个最大值。 输入：N，然后是NN个绝对值不超过128的整数 输出：最大子矩阵的和 问题分析：枚举子矩阵最上和最下的行以及最左和最右的列，但仅这样就已经是O（N^4）的复杂度了。对于N