2021-07-30-poj-1050

经典动态规划：最大子矩阵
在解决这个二维问题前应该首先解决一维问题：最大连续子段和,这也是个动态规划问题
同样，最大子矩阵这个二维问题可以由一维的最大连续子段和问题递推出求解方法(然而我在学会了一维解法后并不会推出二维解法)
最大子矩阵解法
对上面这个解法代码的一点说明：
i是穷举最大子矩阵的起始上界，j是穷举最大子矩阵的下界，然后在这个区间内把所有列求和(由于i和j在不断的变化，所以temprow必须清零，因为temprow保存的是列和),然后对列和求最大连续子段和，列和的最大连续子段和的下界就是最大子矩阵的右界(在动态规划求最大连续子段和中，左界是不知道的)，所以解法的核心其实用了一部分的穷举，真正核心的动态规划是求最大连续子段和的，正是这个算法降低了复杂度，使得蛮力穷举的时间复杂度O(n4)变为了O(n3)。

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容