{"id":2178,"date":"2016-09-10T10:27:32","date_gmt":"2016-09-10T02:27:32","guid":{"rendered":"http:\/\/boweihe.me\/?p=2178"},"modified":"2016-09-10T10:27:32","modified_gmt":"2016-09-10T02:27:32","slug":"leetcode-64-minimum-path-sum","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=2178","title":{"rendered":"LeetCode 64. Minimum Path Sum"},"content":{"rendered":"<h3>\u601d\u8def<\/h3>\n<p>\u52a8\u6001\u89c4\u5212\u7684\u95ee\u9898\uff0c\u67d0\u4e00\u683c\u7684\u72b6\u6001\u7531\u5b83\u5de6\u4fa7\u53ca\u4e0a\u4fa7\u7684\u72b6\u6001\u51b3\u5b9a\uff0c\u5373<br \/>\n[latex]minVal[x][y] = min( minVal[x-1][y], minVal[x][y-1] )[\/latex]<br \/>\n\u5f53\u7136\u4e86\uff0c\u7b2c\u4e00\u884c\u53ea\u7531\u5de6\u4fa7\u51b3\u5b9a\uff0c\u7b2c\u4e00\u5217\u53ea\u7531\u4e0a\u4fa7\u51b3\u5b9a\u3002<\/p>\n<h3>\u4ee3\u7801<\/h3>\n<pre class=\"lang:c++ decode:true \">class Solution {\npublic:\n    int min(int x, int y){\n        return x&lt;y ? x : y;\n    }\n    int minPathSum(vector&lt;vector&lt;int&gt;&gt;&amp; grid) {\n        const int m = grid.size();\n        if(m == 0)\n            return 0;\n        const int n = grid[0].size();\n        for(int i=0; i&lt;m; i++){\n            for(int j=0; j&lt;n; j++){\n                if(i==0 &amp;&amp; j==0)\n                    continue;\n                if(i == 0){\n                    \/\/ min[0][i] = grid[0][i] + min[0][i-1]\n                    grid[i][j] += grid[i][j-1];\n                } else if(j == 0){\n                    grid[i][j] += grid[i-1][j];\n                } else {\n                    grid[i][j] += min(grid[i-1][j], grid[i][j-1]);\n                }\n            }\n        }\n        return grid[m-1][n-1];\n    }\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u601d\u8def \u52a8\u6001\u89c4\u5212\u7684\u95ee\u9898\uff0c\u67d0\u4e00\u683c\u7684\u72b6\u6001\u7531\u5b83\u5de6\u4fa7\u53ca\u4e0a\u4fa7\u7684\u72b6\u6001\u51b3\u5b9a\uff0c\u5373 [latex]minVal[x][y] = min( minVal[x-1][y], minVal[x][y-1] )[\/latex] \u5f53\u7136\u4e86\uff0c\u7b2c\u4e00\u884c\u53ea\u7531\u5de6\u4fa7\u51b3\u5b9a\uff0c\u7b2c\u4e00\u5217\u53ea\u7531\u4e0a\u4fa7\u51b3\u5b9a\u3002 \u4ee3\u7801 class Solution { public: int min(int x, int y){ return x&lt;y ? x : y; } int minPathSum(vector&lt;vector&lt;int&gt;&gt;&amp; grid) { const int m = grid.size(); if(m == 0) return 0; const int n = grid[0].size(); for(int i=0; i&lt;m; i++){ for(int j=0; j&lt;n; j++){ if(i==0 &amp;&amp; [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[66,141],"class_list":["post-2178","post","type-post","status-publish","format-standard","hentry","category-study","tag-leetcode-oj","tag-141"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2178","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2178"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2178\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2178"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2178"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2178"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}