{"id":4226,"date":"2018-10-28T08:45:22","date_gmt":"2018-10-28T15:45:22","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4226"},"modified":"2018-10-28T08:49:43","modified_gmt":"2018-10-28T15:49:43","slug":"leetcode-931-minimum-falling-path-sum","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-931-minimum-falling-path-sum\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 931. Minimum Falling Path Sum"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

Given a\u00a0square<\/strong>\u00a0array of integers\u00a0A<\/code>, we want the\u00a0minimum<\/strong>\u00a0sum of a\u00a0falling path<\/em>\u00a0through\u00a0A<\/code>.<\/p>\n

A falling path starts at any element in the first row, and chooses one element from each row.\u00a0 The next row’s choice must be in a column that is different from the previous row’s column by at most one.<\/p>\n

 <\/p>\n

Example 1:<\/strong><\/p>\n

Input: <\/strong>[[1,2,3],[4,5,6],[7,8,9]]<\/span>\r\nOutput: <\/strong>12<\/span>\r\nExplanation: <\/strong>\r\nThe possible falling paths are:\r\n<\/pre>\n
    \n
  • [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]<\/code><\/li>\n
  • [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]<\/code><\/li>\n
  • [3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]<\/code><\/li>\n<\/ul>\n
    The falling path with the smallest sum is\u00a0[1,4,7]<\/code>, so the answer is\u00a012<\/code>.<\/p>\n
    Note:<\/strong><\/p>\n
      \n
    1. 1 <= A.length == A[0].length <= 100<\/code><\/li>\n
    2. -100 <= A[i][j] <= 100<\/code><\/li>\n<\/ol>\n
      Solution: DP<\/strong><\/h1>\n
      Time complexity: O(mn)<\/p>\n
      Space complexity: O(mn)<\/p>\n
      \n
      C++<\/h2>\n
      \n\n
      \/\/ Author: Huahua, 12 ms\r\nclass Solution {\r\npublic:\r\n  int minFallingPathSum(vector<vector<int>>& A) {\r\n    int n = A.size();\r\n    int m = A[0].size();\r\n    vector<vector<int>> dp(n + 2, vector<int>(m + 2));\r\n          \r\n    for (int i = 1; i <= n; ++i) {\r\n      dp[i][0] = dp[i][m + 1] = INT_MAX;\r\n      for (int j = 1; j <= m; ++j)\r\n        dp[i][j] = *min_element(dp[i - 1].begin() + j - 1, \r\n                                dp[i - 1].begin() + j + 2) + A[i - 1][j - 1];      \r\n    }\r\n    return *min_element(dp[n].begin() + 1, dp[n].end() - 1);\r\n  }\r\n};<\/pre>\n\n<\/div>
      C++\/in place<\/h2>\n
      \n\n
      \/\/ Author: Huahua, 12 ms\r\nclass Solution {\r\npublic:\r\n  int minFallingPathSum(vector<vector<int>>& A) {\r\n    int n = A.size();\r\n    int m = A[0].size();    \r\n          \r\n    for (int i = 1; i < n; ++i)\r\n      for (int j = 0; j < m; ++j) {\r\n        int sum = A[i - 1][j];\r\n        if (j > 0) sum = min(sum, A[i - 1][j - 1]);\r\n        if (j < m - 1) sum = min(sum, A[i - 1][j + 1]);\r\n        A[i][j] += sum;\r\n      }\r\n            \r\n    return *min_element(begin(A.back()), end(A.back()));\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
      Problem Given a\u00a0square\u00a0array of integers\u00a0A, we want the\u00a0minimum\u00a0sum of a\u00a0falling path\u00a0through\u00a0A. A falling path starts at any element in the first row, and chooses one…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,177,116],"class_list":["post-4226","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-medium","tag-path","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4226","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4226"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4226\/revisions"}],"predecessor-version":[{"id":4229,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4226\/revisions\/4229"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4226"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4226"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4226"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}