{"id":2555,"date":"2018-05-06T20:45:20","date_gmt":"2018-05-06T12:45:20","guid":{"rendered":"https:\/\/boweihe.me\/?p=2555"},"modified":"2018-05-06T20:45:20","modified_gmt":"2018-05-06T12:45:20","slug":"leetcode-lis%e7%b3%bb%e5%88%97","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=2555","title":{"rendered":"LeetCode LIS\u7cfb\u5217 (Longest Increasing Path in a Matrix)"},"content":{"rendered":"

\u7c7b\u4f3c\u7684\u4e1c\u897f\u8fd8\u6709\uff1a
\n674.\u00a0Longest Continuous Increasing Subsequence<\/strong>
\nhttps:\/\/leetcode.com\/problems\/longest-continuous-increasing-subsequence\/description\/
\n300.\u00a0Longest Increasing Subsequence<\/strong>
\nhttps:\/\/leetcode.com\/problems\/longest-increasing-subsequence\/description\/
\nlongest path increasing by 1<\/strong>
\nhttps:\/\/www.geeksforgeeks.org\/find-the-longest-path-in-a-matrix-with-given-constraints\/
\n 
\n\u4e0b\u9762\u7684\u4ee3\u7801\u662f\u8fd9\u4e2a\u9898\u7684\uff1a<\/p>\n

\n

329.\u00a0Longest Increasing Path in a Matrix<\/h3>\n<\/div>\n

https:\/\/leetcode.com\/problems\/longest-increasing-path-in-a-matrix\/description\/\u00a0<\/a>
\n\u4e3b\u8981\u601d\u8def\u5c31\u662f\u778eJB\u641c\u7d22\uff0c\u4e0d\u8fc7\u67d0\u4e00\u4e2a\u4f4d\u7f6e\u7684\u7ed3\u679c\u53ef\u4ee5\u8bb0\u5f55\u4e0b\u6765\u7ed9\u540e\u7eed\u7684\u91cd\u590d\u641c\u7d22\u4f7f\u7528\u3002<\/p>\n

class Solution {\npublic:\n\tint subLIP(vector<vector<int>>& matrix, vector<vector<int>>& sub_results, int row, int col)\n\t{\n\t\tif (row < 0 || row >= matrix.size())\n\t\t\treturn 0;\n\t\tif (col < 0 || col >= matrix[0].size())\n\t\t\treturn 0;\n\t\tif (sub_results[row][col] != -1)\n\t\t\treturn sub_results[row][col];\n\t\t\/\/ go left\n\t\tint maxResult = -1;\n\t\tif (col > 0 && matrix[row][col - 1] > matrix[row][col])\n\t\t\tmaxResult = max(maxResult, 1 + subLIP(matrix, sub_results, row, col - 1));\n\t\t\/\/ go right\n\t\tif (col < matrix[0].size() - 1 && matrix[row][col + 1] > matrix[row][col])\n\t\t\tmaxResult = max(maxResult, 1 + subLIP(matrix, sub_results, row, col + 1));\n\t\t\/\/ go up\n\t\tif (row > 0 && matrix[row - 1][col] > matrix[row][col])\n\t\t\tmaxResult = max(maxResult, 1 + subLIP(matrix, sub_results, row - 1, col));\n\t\t\/\/ go down\n\t\tif (row < matrix.size() - 1 && matrix[row + 1][col] > matrix[row][col])\n\t\t\tmaxResult = max(maxResult, 1 + subLIP(matrix, sub_results, row + 1, col));\n\t\tsub_results[row][col] = max(1, maxResult);\n\t\treturn sub_results[row][col];\n\t}\n\tint longestIncreasingPath(vector<vector<int>>& matrix) {\n\t\tvector<vector<int>> sub_results;\n\t\tsub_results.resize(matrix.size());\n\t\tfor (int i = 0; i < matrix.size(); ++i)\n\t\t{\n\t\t\tsub_results[i].resize(matrix[0].size(), -1);   \/\/ -1 means unknown\n\t\t}\n\t\tint result = 0;\n\t\tfor (int r = 0; r < matrix.size(); ++r)\n\t\t{\n\t\t\tfor (int c = 0; c < matrix[r].size(); ++c)\n\t\t\t{\n\t\t\t\tresult = max(result, subLIP(matrix, sub_results, r, c));\n\t\t\t}\n\t\t}\n\t\treturn result;\n\t}\n};<\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
\u7c7b\u4f3c\u7684\u4e1c\u897f\u8fd8\u6709\uff1a 674.\u00a0Longest Continuous Increasing Subsequence https:\/\/leetcode.com\/problems\/longest-continuous-increasing-subsequence\/description\/ 300.\u00a0Longest Increasing Subsequence https:\/\/leetcode.com\/problems\/longest-increasing-subsequence\/description\/ longest path increasing by 1 https:\/\/www.geeksforgeeks.org\/find-the-longest-path-in-a-matrix-with-given-constraints\/   \u4e0b\u9762\u7684\u4ee3\u7801\u662f\u8fd9\u4e2a\u9898\u7684\uff1a 329.\u00a0Longest Increasing Path in a Matrix https:\/\/leetcode.com\/problems\/longest-increasing-path-in-a-matrix\/description\/\u00a0 \u4e3b\u8981\u601d\u8def\u5c31\u662f\u778eJB\u641c\u7d22\uff0c\u4e0d\u8fc7\u67d0\u4e00\u4e2a\u4f4d\u7f6e\u7684\u7ed3\u679c\u53ef\u4ee5\u8bb0\u5f55\u4e0b\u6765\u7ed9\u540e\u7eed\u7684\u91cd\u590d\u641c\u7d22\u4f7f\u7528\u3002 class Solution { public: int subLIP(vector<vector<int>>& matrix, vector<vector<int>>& sub_results, int row, int col) { if (row < 0 || row >= matrix.size()) return 0; if (col < 0 || […]<\/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],"class_list":["post-2555","post","type-post","status-publish","format-standard","hentry","category-study","tag-leetcode-oj"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2555","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=2555"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2555\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2555"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2555"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2555"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}