{"id":2686,"date":"2022-04-10T00:15:06","date_gmt":"2022-04-09T16:15:06","guid":{"rendered":"https:\/\/www.zeroheart.xyz\/wordpress\/?p=2686"},"modified":"2022-04-10T00:38:29","modified_gmt":"2022-04-09T16:38:29","slug":"dp%e7%ac%ac14%e5%a4%a9","status":"publish","type":"post","link":"https:\/\/www.zeroheart.xyz\/wordpress\/?p=2686","title":{"rendered":"dp\u7b2c14\u5929"},"content":{"rendered":"\n

1314. \u77e9\u9635\u533a\u57df\u548c<\/a><\/p>\n\n\n\n

\u8fd9\u9898\u7684\u57fa\u7840\u662f\u524d\u7f00\u548c\uff0c\u540e\u9762\u4f30\u8ba1\u4e5f\u4f1a\u505a\u5230\uff0c\u8fd9\u9898\u7684\u8fb9\u754c\u6bd4\u8f83\u96be\u63a7\u5236\uff0c\u503c\u7684\u591a\u770b\u51e0\u904d\u3002<\/p>\n\n\n\n

\u524d\u7f00\u548c\uff0c\u5c31\u662f\uff080\uff0c0\uff09\u5230(i,j)\u8fd9\u91cc\u7684\u5143\u7d20\u7684\u548c\uff0ck\u4ee3\u8868\uff08i,j\uff09\u56db\u5468\u4e3e\u4f8b\u4e3ak\u7684\u6b63\u65b9\u5f62\uff0c\u8f93\u51fa\u533a\u57df\u7684\u548c\uff0c\u516c\u5f0f dp[i][j] = mat[i][j] + dp[i-1][j] + dp[i][j-1] – dp[i-1][j-1];i,j\u4ece1\u5f00\u59cb\uff0c\u56e0\u4e3a\u5916\u5c42\u8865\u4e86\u4e00\u5c420<\/p>\n\n\n\n

\u611f\u8c22\u8fd9\u4e2a\u5927\u5144\u5f1f\u7684\u56fe https:\/\/leetcode-cn.com\/problems\/matrix-block-sum\/solution\/lei-qian-zhui-he-dong-tai-gui-hua-hua-tu-53z6\/<\/p>\n\n\n\n

\/**\n 1314. \u77e9\u9635\u533a\u57df\u548c\n \u7ed9\u4f60\u4e00\u4e2a m x n \u7684\u77e9\u9635 mat \u548c\u4e00\u4e2a\u6574\u6570 k \uff0c\u8bf7\u4f60\u8fd4\u56de\u4e00\u4e2a\u77e9\u9635 answer \uff0c\u5176\u4e2d\u6bcf\u4e2a answer[i][j] \u662f\u6240\u6709\u6ee1\u8db3\u4e0b\u8ff0\u6761\u4ef6\u7684\u5143\u7d20 mat[r][c] \u7684\u548c\uff1a\n\n i - k <= r <= i + k,\n j - k <= c <= j + k \u4e14\n (r, c) \u5728\u77e9\u9635\u5185\u3002\n\n\n \u793a\u4f8b 1\uff1a\n\n \u8f93\u5165\uff1amat = [[1,2,3],[4,5,6],[7,8,9]], k = 1\n \u8f93\u51fa\uff1a[[12,21,16],[27,45,33],[24,39,28]]\n \u793a\u4f8b 2\uff1a\n\n \u8f93\u5165\uff1amat = [[1,2,3],[4,5,6],[7,8,9]], k = 2\n \u8f93\u51fa\uff1a[[45,45,45],[45,45,45],[45,45,45]]\n\n\n \u63d0\u793a\uff1a\n\n m == mat.length\n n == mat[i].length\n 1 <= m, n, k <= 100\n 1 <= mat[i][j] <= 100\n\n * @author zeroheart\n *\n *\/\npublic class Question1314 {\n    public int[][] matrixBlockSum(int[][] mat, int k) {\n        \/\/ \u8fd9\u9898\u5355\u72ec\u770b\u9898\u76ee\uff0c\u4e00\u5f00\u59cb\u662f\u5b8c\u5168\u4e0d\u77e5\u6240\u4e91\u7684\u3002\u770b\u4e86\u4e00\u4e9b\u56fe\u89e3\u624d\u77e5\u9053\u8981\u505a\u7684\u4e8b\u60c5\u3002\n        \/\/ 1.\u524d\u7f00\u548c\uff0c\u5c31\u662f\uff080\uff0c0\uff09\u5230(i,j)\u8fd9\u91cc\u7684\u5143\u7d20\u7684\u548c\uff0ck\u4ee3\u8868\uff08i,j\uff09\u56db\u5468\u4e3e\u4f8b\u4e3ak\u7684\u6b63\u65b9\u5f62\uff0c\u8f93\u51fa\u533a\u57df\u7684\u548c\u3002\n        \/\/ \u611f\u8c22\u8fd9\u4e2a\u5927\u5144\u5f1f\u7684\u56fe https:\/\/leetcode-cn.com\/problems\/matrix-block-sum\/solution\/lei-qian-zhui-he-dong-tai-gui-hua-hua-tu-53z6\/\n        int m = mat.length;\n        int n = mat[0].length;\n        int[][] dp = new int[m+1][n+1]; \/\/ \u5728\u5de6\u8fb9\u548c\u4e0a\u9762\u52a0\u4e86\u4e00\u63920\uff0cdp[1][1]\u5b9e\u9645\u5c31\u662fdp[0][0]\n\n        int[][] res = new int[m][n]; \/\/ \u5728\u5de6\u8fb9\u548c\u4e0a\u9762\u52a0\u4e86\u4e00\u63920\uff0cdp[1][1]\u5b9e\u9645\u5c31\u662fdp[0][0]\n\n        for(int i = 1;i<=m;i++){\n            for(int j = 1;j<=n;j++){\n                dp[i][j] = mat[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];\n            }\n        }\n\n        for(int i=0; i<m; i++){\n            for(int j=0; j<n; j++){\n                int x = Math.max(i-k, 0);\n                int x1 = Math.min(i+k, m-1);\n                int y = Math.max(j-k, 0);\n                int y1 = Math.min(j+k, n-1);\n\n                res[i][j] = dp[x1+1][y1+1] - dp[x1+1][y] - dp[x][y1+1] + dp[x][y];\n            }\n        }\n        return res;\n\n    }\n\n    public static void main(String[] args) {\n    }\n}\n<\/pre>\n\n\n\n
304. \u4e8c\u7ef4\u533a\u57df\u548c\u68c0\u7d22 – \u77e9\u9635\u4e0d\u53ef\u53d8<\/a><\/p>\n\n\n\n
\u8fd9\u4e00\u9898\u76f4\u63a5\u5de9\u56fa\u4e86\u4e0a\u9762\u7684\u7ed3\u8bba\uff0c\u76f4\u63a5\u7528\u524d\u7f00\u548c+\u9762\u79ef\u5185\u548c\u7684\u505a\u6cd5\u5c31\u884c\uff0c\u5728\u5199\u4e00\u4e0b\u516c\u5f0f<\/p>\n\n\n\n
1.\u524d\u7f00\u548c\uff1adp[i][j] = mat[i][j] + dp[i-1][j] + dp[i][j-1] – dp[i-1][j-1];i,j\u4ece1\u5f00\u59cb\uff0c\u56e0\u4e3a\u5916\u5c42\u8865\u4e86\u4e00\u5c420<\/p>\n\n\n\n
2.\u9762\u79ef\u5185\u548cres[i][j] = dp[x1+1][y1+1] – dp[x1+1][y] – dp[x][y1+1] + dp[x][y];x1<=m-1;y1<=n-1;<\/p>\n\n\n\n
\/**
<\/em> 304. \u4e8c\u7ef4\u533a\u57df\u548c\u68c0\u7d22 - \u77e9\u9635\u4e0d\u53ef\u53d8
<\/em> \u7ed9\u5b9a\u4e00\u4e2a\u4e8c\u7ef4\u77e9\u9635 matrix\uff0c\u4ee5\u4e0b\u7c7b\u578b\u7684\u591a\u4e2a\u8bf7\u6c42\uff1a
<\/em>
<\/em> \u8ba1\u7b97\u5176\u5b50\u77e9\u5f62\u8303\u56f4\u5185\u5143\u7d20\u7684\u603b\u548c\uff0c\u8be5\u5b50\u77e9\u9635\u7684 \u5de6\u4e0a\u89d2 \u4e3a (row1, col1) \uff0c\u53f3\u4e0b\u89d2 \u4e3a (row2, col2) \u3002
<\/em> \u5b9e\u73b0 NumMatrix \u7c7b\uff1a
<\/em>
<\/em> NumMatrix(int[][] matrix) \u7ed9\u5b9a\u6574\u6570\u77e9\u9635 matrix \u8fdb\u884c\u521d\u59cb\u5316
<\/em> int sumRegion(int row1, int col1, int row2, int col2) \u8fd4\u56de \u5de6\u4e0a\u89d2 (row1, col1) \u3001\u53f3\u4e0b\u89d2 (row2, col2) \u6240\u63cf\u8ff0\u7684\u5b50\u77e9\u9635\u7684\u5143\u7d20 \u603b\u548c \u3002
<\/em>
<\/em>
<\/em> \u793a\u4f8b 1\uff1a
<\/em>
<\/em>
<\/em>
<\/em> \u8f93\u5165:
<\/em> [\"NumMatrix\",\"sumRegion\",\"sumRegion\",\"sumRegion\"]
<\/em> [[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
<\/em> \u8f93\u51fa:
<\/em> [null, 8, 11, 12]
<\/em>
<\/em> \u89e3\u91ca:
<\/em> NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);
<\/em> numMatrix.sumRegion(2, 1, 4, 3); \/\/ return 8 (\u7ea2\u8272\u77e9\u5f62\u6846\u7684\u5143\u7d20\u603b\u548c)
<\/em> numMatrix.sumRegion(1, 1, 2, 2); \/\/ return 11 (\u7eff\u8272\u77e9\u5f62\u6846\u7684\u5143\u7d20\u603b\u548c)
<\/em> numMatrix.sumRegion(1, 2, 2, 4); \/\/ return 12 (\u84dd\u8272\u77e9\u5f62\u6846\u7684\u5143\u7d20\u603b\u548c)
<\/em>
<\/em>
<\/em> \u63d0\u793a\uff1a
<\/em>
<\/em> m == matrix.length
<\/em> n == matrix[i].length
<\/em> 1 <= m, n <= 200
<\/em> -105 <= matrix[i][j] <= 105
<\/em> 0 <= row1 <= row2 < m
<\/em> 0 <= col1 <= col2 < n
<\/em> \u6700\u591a\u8c03\u7528 104 \u6b21 sumRegion \u65b9\u6cd5
<\/em>
<\/em> * <\/em>@author <\/em><\/strong>zeroheart
<\/em> *
<\/em> *\/
<\/em>public class Question304 {
    int[][] dp;
    public void NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        dp = new int[m+1][n+1];

        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                dp[i][j] = matrix[i-1][j-1] + dp[i-1][j] + dp[i][j-1] -  dp[i-1][j-1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2+1][col2+1] - dp[row1][col2+1] - dp[row2+1][col1] + dp[row1][col1];
    }

    public static void main(String[] args) {
    }
}<\/pre>\n","protected":false},"excerpt":{"rendered":"
1314. \u77e9\u9635\u533a\u57df\u548c \u8fd9\u9898\u7684\u57fa\u7840\u662f\u524d\u7f00\u548c\uff0c\u540e\u9762\u4f30\u8ba1\u4e5f\u4f1a\u505a\u5230\uff0c\u8fd9\u9898\u7684\u8fb9\u754c\u6bd4\u8f83\u96be\u63a7\u5236\uff0c\u503c\u7684\u591a\u770b\u51e0\u904d\u3002 \u524d\u7f00\u548c\uff0c\u5c31 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[155],"tags":[158,195],"_links":{"self":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2686"}],"collection":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2686"}],"version-history":[{"count":10,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2686\/revisions"}],"predecessor-version":[{"id":2696,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2686\/revisions\/2696"}],"wp:attachment":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2686"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2686"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2686"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}