{"id":101570,"date":"2026-09-07T00:37:14","date_gmt":"2026-09-06T16:37:14","guid":{"rendered":"https:\/\/www.wsisp.com\/helps\/101570.html"},"modified":"2026-09-07T00:37:14","modified_gmt":"2026-09-06T16:37:14","slug":"%e7%ae%97%e6%b3%9533%ef%bc%8c%e7%9f%a9%e9%98%b5%e5%8c%ba%e5%9f%9f%e6%b1%82%e5%92%8c%ef%bc%8c%e4%ba%8c%e7%bb%b4%e5%89%8d%e7%bc%80%e5%92%8c","status":"publish","type":"post","link":"https:\/\/www.wsisp.com\/helps\/101570.html","title":{"rendered":"\u7b97\u6cd533\uff0c\u77e9\u9635\u533a\u57df\u6c42\u548c\uff0c\u4e8c\u7ef4\u524d\u7f00\u548c"},"content":{"rendered":"<\/p>\n

\u4e00\u3001\u9884\u5904\u7406：\u6c42 dp[i][j]<\/h3>\n

\u5b9a\u4e49 dp[i][j] = \u4ece\u5de6\u4e0a\u89d2 (1,1) \u5230 (i,j) \u8fd9\u4e2a\u77e9\u5f62\u5185\u6240\u6709\u5143\u7d20\u7684\u548c\u3002<\/p>\n

\u9012\u63a8\u65f6，\u5f53\u524d\u683c (i,j) \u7684\u77e9\u5f62\u7531\u56db\u5757\u62fc\u6210：<\/p>\n

dp[i][j]=dp[i\u22121][j]+dp[i][j\u22121]\u2212dp[i\u22121][j\u22121]+a[i][j]<\/p>\n

\u5373：\u4e0a\u9762\u6574\u5757 A + \u5de6\u8fb9\u6574\u5757 B \u2212 \u91cd\u590d\u7b97\u4e86\u4e00\u6b21\u7684\u5de6\u4e0a\u89d2 C + \u81ea\u5df1\u3002\u8fd9\u5c31\u662f\u4f60\u7b14\u8bb0\u91cc A+B\u2212C+D \u7684\u90a3\u4e00\u7b14（D \u662f\u5f53\u524d\u683c）\u3002<\/p>\n

\u4e8c\u3001\u67e5\u8be2：\u6c42\u4efb\u610f\u5b50\u77e9\u9635\u7684\u548c<\/h3>\n

\u8981\u6c42\u5de6\u4e0a\u89d2 (x1,y1)\u3001\u53f3\u4e0b\u89d2 (x2,y2) \u7684\u533a\u57df\u548c：<\/p>\n

sum=dp[x2\u200b][y2\u200b]\u2212dp[x1\u200b\u22121][y2\u200b]\u2212dp[x2\u200b][y1\u200b\u22121]+dp[x1\u200b\u22121][y1\u200b\u22121]<\/p>\n

\u53e3\u8bc0：\u5927\u77e9\u5f62 \u2212 \u4e0a\u9762 \u2212 \u5de6\u8fb9 + \u88ab\u591a\u51cf\u4e86\u4e00\u6b21\u7684\u5de6\u4e0a\u89d2\u3002<\/p>\n

\u8fd9\u6837\u5355\u6b21\u67e5\u8be2\u4ece O(\u9762\u79ef) \u964d\u5230 O(1)\u3002<\/p>\n

\u4e09\u3001\u7528\u624b\u91cc\u7684 3\u00d73 \u77e9\u9635\u63a8\u4e00\u904d<\/h3>\n

\u4ee5\u77e9\u9635\u4e3a\u4f8b：<\/p>\n

1 2 3
\n4 5 6
\n7 8 9<\/p>\n

\u5bf9\u5e94\u7684 dp（1-indexed）：<\/p>\n\n\n

j=1<\/p>\n

j=2<\/p>\n

j=3<\/p>\n<\/tr>\n

\n\n\n\n
\n

i=1\u200b<\/p>\n<\/td>\n

\n

1<\/p>\n<\/td>\n

\n

3<\/p>\n<\/td>\n

\n

6<\/p>\n<\/td>\n<\/tr>\n

\n

i=2\u200b<\/p>\n<\/td>\n

\n

5<\/p>\n<\/td>\n

\n

12<\/p>\n<\/td>\n

\n

21<\/p>\n<\/td>\n<\/tr>\n

\n

i=3\u200b<\/p>\n<\/td>\n

\n

12<\/p>\n<\/td>\n

\n

27<\/p>\n<\/td>\n

\n

45<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

\u9a8c\u7b97\u53f3\u4e0b\u89d2 2\u00d72（(2,2)~(3,3)，\u5b9e\u9645\u662f 5+6+8+9=28）：<\/p>\n

45\u2212dp[1][3]\u2212dp[3][1]+dp[1][1]=45\u22126\u221212+1=28\u2713<\/p>\n

\u56db\u3001\u8fb9\u754c\u5904\u7406（\u7b14\u8bb0\u91cc\u7684 max \/ min）<\/h3>\n

\u9898\u76ee\u5e38\u7ed9"\u4ee5 (x,y) \u4e3a\u4e2d\u5fc3\u3001\u534a\u5f84\u4e3a r \u7684\u77e9\u5f62"（\u5982 LeetCode 1314），\u5750\u6807\u4f1a\u8d8a\u754c，\u5fc5\u987b\u5148 clamp\u200b \u518d\u67e5\u8be2：<\/p>\n

int x1 = Math.max(0, i – r), x2 = Math.min(m – 1, i + r);
\nint y1 = Math.max(0, j – r), y2 = Math.min(n – 1, j + r);<\/p>\n

\u8fd9\u662f 0-indexed \u5199\u6cd5；\u82e5 dp \u7528 1-indexed，\u5219 clamp \u5230 [1, m] \/ [1, n]，\u4e24\u8fb9\u522b\u6df7\u7528\u3002<\/p>\n

\u4e94\u3001Java \u4ee3\u7801<\/h3>\n

\u2460 \u9884\u5904\u7406 + \u67e5\u8be2（LeetCode 304）<\/p>\n

class NumMatrix {
\n private int[][] dp; \/\/ dp[i+1][j+1] \u5bf9\u5e94\u524d i+1 \u884c\u3001j+1 \u5217<\/p>\n

public NumMatrix(int[][] matrix) {
\n int m = matrix.length, n = matrix[0].length;
\n dp = new int[m + 1][n + 1]; \/\/ \u591a\u5f00\u4e00\u884c\u4e00\u5217\u5f53\u54e8\u5175
\n for (int i = 1; i <= m; i++)
\n for (int j = 1; j <= n; j++)
\n dp[i][j] = dp[i-1][j] + dp[i][j-1]
\n – dp[i-1][j-1] + matrix[i-1][j-1];
\n }<\/p>\n

\/\/ \u8fd4\u56de 0-indexed \u7684 [row1,row2] \u00d7 [col1,col2] \u533a\u57df\u548c
\n public int sumRegion(int row1, int col1, int row2, int col2) {
\n return dp[row2+1][col2+1]
\n – dp[row1][col2+1]
\n – dp[row2+1][col1]
\n + dp[row1][col1];
\n }
\n}<\/p>\n

\u2461 \u77e9\u9635\u533a\u57df\u548c（LeetCode 1314，\u542b\u8fb9\u754c clamp）<\/p>\n

public int[][] matrixBlockSum(int[][] mat, int r) {
\n int m = mat.length, n = mat[0].length;
\n int[][] dp = new int[m + 1][n + 1];
\n for (int i = 1; i <= m; i++)
\n for (int j = 1; j <= n; j++)
\n dp[i][j] = dp[i-1][j] + dp[i][j-1]
\n – dp[i-1][j-1] + mat[i-1][j-1];<\/p>\n

int[][] ans = new int[m][n];
\n for (int i = 0; i < m; i++) {
\n for (int j = 0; j < n; j++) {
\n int x1 = Math.max(0, i – r), x2 = Math.min(m – 1, i + r);
\n int y1 = Math.max(0, j – r), y2 = Math.min(n – 1, j + r);
\n ans[i][j] = dp[x2+1][y2+1] – dp[x1][y2+1]
\n – dp[x2+1][y1] + dp[x1][y1];
\n }
\n }
\n return ans;
\n}<\/p>\n

\u590d\u6742\u5ea6：\u9884\u5904\u7406 O(mn)\u3001\u7a7a\u95f4 O(mn)，\u6bcf\u6b21\u67e5\u8be2 O(1)\u3002<\/p>\n

<\/h3><\/p>\n","protected":false},"excerpt":{"rendered":"

\u4e00\u3001\u9884\u5904\u7406：\u6c42 dp[i][j]\u5b9a\u4e49 dp[i][j] \u4ece\u5de6\u4e0a\u89d2 (1,1) \u5230 (i,j) \u8fd9\u4e2a\u77e9\u5f62\u5185\u6240\u6709\u5143\u7d20\u7684\u548c\u3002\u9012\u63a8\u65f6，\u5f53\u524d\u683c (i,j) \u7684\u77e9\u5f62\u7531\u56db\u5757\u62fc\u6210：dp[i][j]dp[i\u22121][j]dp[i][j\u22121]\u2212dp[i\u22121][j\u22121]a[i][j]\u5373：\u4e0a\u9762\u6574\u5757 A \u5de6\u8fb9\u6574\u5757 B \u2212 \u91cd\u590d\u7b97\u4e86\u4e00\u6b21\u7684\u5de6\u4e0a\u89d2 C \u81ea\u5df1\u3002\u8fd9\u5c31\u662f\u4f60\u7b14\u8bb0\u91cc AB\u2212CD \u7684\u90a3\u4e00\u7b14（D \u662f\u5f53\u524d\u683c）\u3002\u4e8c\u3001\u67e5\u8be2<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[1578,427,1649],"topic":[],"class_list":["post-101570","post","type-post","status-publish","format-standard","hentry","category-server","tag-1578","tag-427","tag-1649"],"yoast_head":"\n\u7b97\u6cd533\uff0c\u77e9\u9635\u533a\u57df\u6c42\u548c\uff0c\u4e8c\u7ef4\u524d\u7f00\u548c - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.wsisp.com\/helps\/101570.html\" \/>\n<meta property=\"og:locale\" content=\"zh_CN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"\u7b97\u6cd533\uff0c\u77e9\u9635\u533a\u57df\u6c42\u548c\uff0c\u4e8c\u7ef4\u524d\u7f00\u548c - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\" \/>\n<meta property=\"og:description\" content=\"\u4e00\u3001\u9884\u5904\u7406：\u6c42 dp[i][j]\u5b9a\u4e49 dp[i][j] \u4ece\u5de6\u4e0a\u89d2 (1,1) \u5230 (i,j) \u8fd9\u4e2a\u77e9\u5f62\u5185\u6240\u6709\u5143\u7d20\u7684\u548c\u3002\u9012\u63a8\u65f6，\u5f53\u524d\u683c (i,j) \u7684\u77e9\u5f62\u7531\u56db\u5757\u62fc\u6210：dp[i][j]dp[i\u22121][j]dp[i][j\u22121]\u2212dp[i\u22121][j\u22121]a[i][j]\u5373：\u4e0a\u9762\u6574\u5757 A \u5de6\u8fb9\u6574\u5757 B \u2212 \u91cd\u590d\u7b97\u4e86\u4e00\u6b21\u7684\u5de6\u4e0a\u89d2 C \u81ea\u5df1\u3002\u8fd9\u5c31\u662f\u4f60\u7b14\u8bb0\u91cc AB\u2212CD \u7684\u90a3\u4e00\u7b14（D \u662f\u5f53\u524d\u683c）\u3002\u4e8c\u3001\u67e5\u8be2\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.wsisp.com\/helps\/101570.html\" \/>\n<meta property=\"og:site_name\" content=\"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\" \/>\n<meta property=\"article:published_time\" content=\"2026-09-06T16:37:14+00:00\" \/>\n<meta name=\"author\" content=\"admin\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"admin\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 \u5206\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/101570.html\",\"url\":\"https:\/\/www.wsisp.com\/helps\/101570.html\",\"name\":\"\u7b97\u6cd533\uff0c\u77e9\u9635\u533a\u57df\u6c42\u548c\uff0c\u4e8c\u7ef4\u524d\u7f00\u548c - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\",\"isPartOf\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/#website\"},\"datePublished\":\"2026-09-06T16:37:14+00:00\",\"dateModified\":\"2026-09-06T16:37:14+00:00\",\"author\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41\"},\"breadcrumb\":{\"@id\":\"https:\/\/www.wsisp.com\/helps\/101570.html#breadcrumb\"},\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.wsisp.com\/helps\/101570.html\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/101570.html#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u9996\u9875\",\"item\":\"https:\/\/www.wsisp.com\/helps\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"\u7b97\u6cd533\uff0c\u77e9\u9635\u533a\u57df\u6c42\u548c\uff0c\u4e8c\u7ef4\u524d\u7f00\u548c\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#website\",\"url\":\"https:\/\/www.wsisp.com\/helps\/\",\"name\":\"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3\",\"description\":\"\u9999\u6e2f\u670d\u52a1\u5668_\u9999\u6e2f\u4e91\u670d\u52a1\u5668\u8d44\u8baf_\u670d\u52a1\u5668\u5e2e\u52a9\u6587\u6863_\u670d\u52a1\u5668\u6559\u7a0b\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.wsisp.com\/helps\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"zh-Hans\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41\",\"name\":\"admin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-Hans\",\"@id\":\"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery\",\"contentUrl\":\"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery\",\"caption\":\"admin\"},\"sameAs\":[\"http:\/\/wp.wsisp.com\"],\"url\":\"https:\/\/www.wsisp.com\/helps\/author\/admin\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"\u7b97\u6cd533\uff0c\u77e9\u9635\u533a\u57df\u6c42\u548c\uff0c\u4e8c\u7ef4\u524d\u7f00\u548c - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.wsisp.com\/helps\/101570.html","og_locale":"zh_CN","og_type":"article","og_title":"\u7b97\u6cd533\uff0c\u77e9\u9635\u533a\u57df\u6c42\u548c\uff0c\u4e8c\u7ef4\u524d\u7f00\u548c - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","og_description":"\u4e00\u3001\u9884\u5904\u7406：\u6c42 dp[i][j]\u5b9a\u4e49 dp[i][j] \u4ece\u5de6\u4e0a\u89d2 (1,1) \u5230 (i,j) \u8fd9\u4e2a\u77e9\u5f62\u5185\u6240\u6709\u5143\u7d20\u7684\u548c\u3002\u9012\u63a8\u65f6，\u5f53\u524d\u683c (i,j) \u7684\u77e9\u5f62\u7531\u56db\u5757\u62fc\u6210：dp[i][j]dp[i\u22121][j]dp[i][j\u22121]\u2212dp[i\u22121][j\u22121]a[i][j]\u5373：\u4e0a\u9762\u6574\u5757 A \u5de6\u8fb9\u6574\u5757 B \u2212 \u91cd\u590d\u7b97\u4e86\u4e00\u6b21\u7684\u5de6\u4e0a\u89d2 C \u81ea\u5df1\u3002\u8fd9\u5c31\u662f\u4f60\u7b14\u8bb0\u91cc AB\u2212CD \u7684\u90a3\u4e00\u7b14（D \u662f\u5f53\u524d\u683c）\u3002\u4e8c\u3001\u67e5\u8be2","og_url":"https:\/\/www.wsisp.com\/helps\/101570.html","og_site_name":"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","article_published_time":"2026-09-06T16:37:14+00:00","author":"admin","twitter_card":"summary_large_image","twitter_misc":{"\u4f5c\u8005":"admin","\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4":"2 \u5206"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/www.wsisp.com\/helps\/101570.html","url":"https:\/\/www.wsisp.com\/helps\/101570.html","name":"\u7b97\u6cd533\uff0c\u77e9\u9635\u533a\u57df\u6c42\u548c\uff0c\u4e8c\u7ef4\u524d\u7f00\u548c - \u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","isPartOf":{"@id":"https:\/\/www.wsisp.com\/helps\/#website"},"datePublished":"2026-09-06T16:37:14+00:00","dateModified":"2026-09-06T16:37:14+00:00","author":{"@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41"},"breadcrumb":{"@id":"https:\/\/www.wsisp.com\/helps\/101570.html#breadcrumb"},"inLanguage":"zh-Hans","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.wsisp.com\/helps\/101570.html"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.wsisp.com\/helps\/101570.html#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9875","item":"https:\/\/www.wsisp.com\/helps"},{"@type":"ListItem","position":2,"name":"\u7b97\u6cd533\uff0c\u77e9\u9635\u533a\u57df\u6c42\u548c\uff0c\u4e8c\u7ef4\u524d\u7f00\u548c"}]},{"@type":"WebSite","@id":"https:\/\/www.wsisp.com\/helps\/#website","url":"https:\/\/www.wsisp.com\/helps\/","name":"\u7f51\u7855\u4e92\u8054\u5e2e\u52a9\u4e2d\u5fc3","description":"\u9999\u6e2f\u670d\u52a1\u5668_\u9999\u6e2f\u4e91\u670d\u52a1\u5668\u8d44\u8baf_\u670d\u52a1\u5668\u5e2e\u52a9\u6587\u6863_\u670d\u52a1\u5668\u6559\u7a0b","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.wsisp.com\/helps\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"zh-Hans"},{"@type":"Person","@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/358e386c577a3ab51c4493330a20ad41","name":"admin","image":{"@type":"ImageObject","inLanguage":"zh-Hans","@id":"https:\/\/www.wsisp.com\/helps\/#\/schema\/person\/image\/","url":"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery","contentUrl":"https:\/\/gravatar.wp-china-yes.net\/avatar\/?s=96&d=mystery","caption":"admin"},"sameAs":["http:\/\/wp.wsisp.com"],"url":"https:\/\/www.wsisp.com\/helps\/author\/admin"}]}},"_links":{"self":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts\/101570","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/comments?post=101570"}],"version-history":[{"count":0,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/posts\/101570\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/media?parent=101570"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/categories?post=101570"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/tags?post=101570"},{"taxonomy":"topic","embeddable":true,"href":"https:\/\/www.wsisp.com\/helps\/wp-json\/wp\/v2\/topic?post=101570"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}