{"id":29,"date":"2022-03-01T21:54:00","date_gmt":"2022-03-01T13:54:00","guid":{"rendered":"https:\/\/blog.49cc.top\/?p=29"},"modified":"2022-03-15T23:27:43","modified_gmt":"2022-03-15T15:27:43","slug":"%e7%a4%bc%e7%89%a9%e7%9a%84%e6%9c%80%e5%a4%a7%e4%bb%b7%e5%80%bc","status":"publish","type":"post","link":"https:\/\/blog.rrr.ink\/?p=29","title":{"rendered":"\u793c\u7269\u7684\u6700\u5927\u4ef7\u503c"},"content":{"rendered":"\n

\u9898\u76ee\u63cf\u8ff0<\/strong>\uff1a<\/p>\n\n\n\n

\u5728\u4e00\u4e2a m*n \u7684\u68cb\u76d8\u7684\u6bcf\u4e00\u683c\u90fd\u653e\u6709\u4e00\u4e2a\u793c\u7269\uff0c\u6bcf\u4e2a\u793c\u7269\u90fd\u6709\u4e00\u5b9a\u7684\u4ef7\u503c\uff08\u4ef7\u503c\u5927\u4e8e 0\uff09\u3002\u4f60\u53ef\u4ee5\u4ece\u68cb\u76d8\u7684\u5de6\u4e0a\u89d2\u5f00\u59cb\u62ff\u683c\u5b50\u91cc\u7684\u793c\u7269\uff0c\u5e76\u6bcf\u6b21\u5411\u53f3\u6216\u8005\u5411\u4e0b\u79fb\u52a8\u4e00\u683c\u3001\u76f4\u5230\u5230\u8fbe\u68cb\u76d8\u7684\u53f3\u4e0b\u89d2\u3002\u7ed9\u5b9a\u4e00\u4e2a\u68cb\u76d8\u53ca\u5176\u4e0a\u9762\u7684\u793c\u7269\u7684\u4ef7\u503c\uff0c\u8bf7\u8ba1\u7b97\u4f60\u6700\u591a\u80fd\u62ff\u5230\u591a\u5c11\u4ef7\u503c\u7684\u793c\u7269\uff1f<\/p>\n\n\n\n

\u793a\u4f8b\uff1a<\/strong><\/p>\n\n\n\n

\u8f93\u5165:<\/strong> \n[\n  [1,3,1],\n  [1,5,1],\n  [4,2,1]\n]<\/code>\n\u8f93\u51fa:<\/strong> 12<\/code>\n\u89e3\u91ca:<\/strong> \u8def\u5f84 1\u21923\u21925\u21922\u21921 \u53ef\u4ee5\u62ff\u5230\u6700\u591a\u4ef7\u503c\u7684\u793c\u7269<\/pre>\n\n\n\n
\u63d0\u793a\uff1a<\/p>\n\n\n\n
  • 0 < grid.length <= 200<\/code><\/li>
  • 0 < grid[0].length <= 200<\/code><\/li><\/ul>\n\n\n\n
    \u601d\u8def\uff1a<\/strong><\/p>\n\n\n\n
    \n
    \u6bd4\u8f83\u57fa\u7840\u7684\u52a8\u6001\u89c4\u5212\u7b97\u6cd5\uff0c\u8f6c\u79fb\u65b9\u7a0b dp[i][j]\uff08\u6240\u5728\u683c\u5b50(i\uff0cj)\u7684\u6700\u5927\u793c\u7269\u4ef7\u503c\uff09=  max(dp[i-1][j],dp[i][j-1]) + grid[i-1][j-1]<\/pre>\n<\/div><\/div>\n\n\n\n
    \u5b9e\u73b0\uff1a<\/strong><\/p>\n\n\n\n
    package main\n\nimport (\n\t\"fmt\"\n)\n\nfunc main() {\n\tgrid  := [][]int{\n\t\t{1, 3, 1},\n\t\t{1, 5, 1},\n\t\t{4, 2, 1},\n\t}\n\tt := maxValue(grid)\n\tfmt.Println(t) \/\/12\n}\n\nfunc maxValue(grid [][]int) int {\n\n\tm, n := len(grid), len(grid[0]) \/\/m*n \u7684\u683c\u5b50\n\n\tif m == 0 || n == 0 {\n\t\treturn 0\n\t}\n\n\n\tdp := make([][]int, m+1)\n\tfor i := 0; i < m+1; i++ {\n\t\tdp[i] = make([]int, n+1)\n\t}\n\n\tfmt.Println(dp)\n\n\tfor i := 1; i < m+1; i++ {\n\t\tfor j := 1; j < n+1; j++ {\n\t\t\t\/\/dp\u503c\u53ea\u4f1a\u53d7\u5230\u4e0a\u65b9\u683c\u5b50\u548c\u5de6\u4fa7\u683c\u5b50\u7684\u5f71\u54cd\n\t\t\t\/\/dp[i][j]\u8868\u793a\u4ecegrid[0][0]\u5230grid[i - 1][j - 1]\u65f6\u7684\u6700\u5927\u4ef7\u503c\n\t\t\tdp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]\n\t\t}\n\t}\n\treturn dp[m][n]\n\n}\n\nfunc max(a, b int) int {\n\tif a > b {\n\t\treturn a\n\t}\n\treturn b\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
    \u9898\u76ee\u63cf\u8ff0\uff1a \u5728\u4e00\u4e2a m*n \u7684\u68cb\u76d8\u7684\u6bcf\u4e00\u683c\u90fd\u653e\u6709\u4e00\u4e2a\u793c\u7269\uff0c\u6bcf\u4e2a\u793c\u7269\u90fd\u6709\u4e00\u5b9a\u7684\u4ef7\u503c\uff08\u4ef7\u503c\u5927\u4e8e 0\uff09\u3002\u4f60\u53ef\u4ee5\u4ece\u68cb\u76d8 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[4],"_links":{"self":[{"href":"https:\/\/blog.rrr.ink\/index.php?rest_route=\/wp\/v2\/posts\/29"}],"collection":[{"href":"https:\/\/blog.rrr.ink\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.rrr.ink\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.rrr.ink\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.rrr.ink\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=29"}],"version-history":[{"count":8,"href":"https:\/\/blog.rrr.ink\/index.php?rest_route=\/wp\/v2\/posts\/29\/revisions"}],"predecessor-version":[{"id":51,"href":"https:\/\/blog.rrr.ink\/index.php?rest_route=\/wp\/v2\/posts\/29\/revisions\/51"}],"wp:attachment":[{"href":"https:\/\/blog.rrr.ink\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=29"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.rrr.ink\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=29"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.rrr.ink\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=29"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}