【深度技术】Dynamic Programming Example:Maximum Sum Submatrix in Matrix



  • 作者:刘帝伟
    原文链接:http://www.csuldw.com/2016/09/14/2016-09-14-maximum-sum-of-a-sub-matrix-in-2d-matrix/
    新浪微博:@拾毅者

    BitTiger坚决尊重拥护原创版权,本文转载已经经过作者授权,如需转载请联系原作者。

    问题描述:

    Find maximum sum submatrix in a given 2D matrix of integers.

    输入:

    0_1476728884450_屏幕快照 2016-10-17 上午11.19.57.png

    返回:

    0_1476728913268_屏幕快照 2016-10-17 上午11.28.25.png

    样例:

    0_1476728976706_屏幕快照 2016-10-17 上午11.29.26.png

    最大连续子序列和

    最大子矩阵与最大连续子序列和有着千丝万缕的联系,最大连续子序列的DP动态转移方程为

    0_1476729017288_屏幕快照 2016-10-17 上午11.30.10.png

    0_1476729043606_屏幕快照 2016-10-17 上午11.30.33.png

    最大子矩阵和

    Step1: 构造行和矩阵

    0_1476729080807_屏幕快照 2016-10-17 上午11.31.11.png

    **Step2:寻找状态转移矩阵

    变量说明**

    0_1476729107982_屏幕快照 2016-10-17 上午11.31.41.png

    解释一

    0_1476729147365_屏幕快照 2016-10-17 上午11.32.18.png

    解释二

    0_1476729193608_屏幕快照 2016-10-17 上午11.33.04.png

    解释三

    0_1476729242542_屏幕快照 2016-10-17 上午11.33.33.png

    1_1476729296705_屏幕快照 2016-10-17 上午11.34.34.png 0_1476729296705_屏幕快照 2016-10-17 上午11.34.44.png

    关于DP,有个博客讲解的非常详实,感兴趣的可以看看,地址:http://www.csie.ntnu.edu.tw/~u91029/DynamicProgramming.html

    References

    Chapter07-_Submatrix_with_largest_sum
    Maximum Sum Rectangular Submatrix in Matrix dynamic programming/2D kadane


登录后回复
 

与 BitTiger Community 的连接断开,我们正在尝试重连,请耐心等待