{"id":9751,"date":"2022-06-14T20:57:20","date_gmt":"2022-06-15T03:57:20","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9751"},"modified":"2022-06-14T21:10:39","modified_gmt":"2022-06-15T04:10:39","slug":"leetcode-2304-minimum-path-cost-in-a-grid","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-2304-minimum-path-cost-in-a-grid\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2304. Minimum Path Cost in a Grid"},"content":{"rendered":"\n

You are given a 0-indexed<\/strong> m x n<\/code> integer matrix grid<\/code> consisting of distinct<\/strong> integers from 0<\/code> to m * n - 1<\/code>. You can move in this matrix from a cell to any other cell in the next<\/strong> row. That is, if you are in cell (x, y)<\/code> such that x < m - 1<\/code>, you can move to any of the cells (x + 1, 0)<\/code>, (x + 1, 1)<\/code>, …, (x + 1, n - 1)<\/code>. Note<\/strong> that it is not possible to move from cells in the last row.<\/p>\n\n\n\n

Each possible move has a cost given by a 0-indexed<\/strong> 2D array moveCost<\/code> of size (m * n) x n<\/code>, where moveCost[i][j]<\/code> is the cost of moving from a cell with value i<\/code> to a cell in column j<\/code> of the next row. The cost of moving from cells in the last row of grid<\/code> can be ignored.<\/p>\n\n\n\n

The cost of a path in grid<\/code> is the sum<\/strong> of all values of cells visited plus the sum<\/strong> of costs of all the moves made. Return the minimum<\/strong> cost of a path that starts from any cell in the first<\/strong> row and ends at any cell in the last<\/strong> row.<\/em><\/p>\n\n\n\n

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

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]\nOutput:<\/strong> 17\nExplanation: <\/strong>The path with the minimum possible cost is the path 5 -> 0 -> 1.\n- The sum of the values of cells visited is 5 + 0 + 1 = 6.\n- The cost of moving from 5 to 0 is 3.\n- The cost of moving from 0 to 1 is 8.\nSo the total cost of the path is 6 + 3 + 8 = 17.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> grid = [[5,1,2],[4,0,3]], moveCost = [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]]\nOutput:<\/strong> 6\nExplanation:<\/strong> The path with the minimum possible cost is the path 2 -> 3.\n- The sum of the values of cells visited is 2 + 3 = 5.\n- The cost of moving from 2 to 3 is 1.\nSo the total cost of this path is 5 + 1 = 6.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • m == grid.length<\/code><\/li>
  • n == grid[i].length<\/code><\/li>
  • 2 <= m, n <= 50<\/code><\/li>
  • grid<\/code> consists of distinct integers from 0<\/code> to m * n - 1<\/code>.<\/li>
  • moveCost.length == m * n<\/code><\/li>
  • moveCost[i].length == n<\/code><\/li>
  • 1 <= moveCost[i][j] <= 100<\/code><\/li><\/ul>\n\n\n\n
    Solution: DP<\/strong><\/h2>\n\n\n\n
    Let dp[i][j] := min cost to reach grid[i][j] from the first row.<\/p>\n\n\n\n
    dp[i][j] = min{grid[i][j] + dp[i – 1][k] + moveCost[grid[i – 1][k]][j]}  0 <= k < n
    <\/p>\n\n\n\n
    For each node, try all possible nodes from the previous row.<\/p>\n\n\n\n
    Time complexity: O(m*n2<\/sup>)
    Space complexity: O(m*n) -> O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int minPathCost(vector>& grid, vector>& moveCost) {\n    const int m = grid.size();\n    const int n = grid[0].size();\n    vector> dp(m, vector(n, INT_MAX));    \n    for (int i = 0; i < m; ++i)\n      for (int j = 0; j < n; ++j)\n        for (int k = 0; k < n; ++k)          \n          dp[i][j] = min(dp[i][j], grid[i][j] + \n                         (i ? dp[i - 1][k] + moveCost[grid[i - 1][k]][j] : 0));\n    return *min_element(begin(dp[m - 1]), end(dp[m - 1]));\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given a 0-indexed m x n integer matrix grid consisting of distinct integers from 0 to m * n – 1. You can move in this matrix from a cell to any other…<\/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],"class_list":["post-9751","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9751","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=9751"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9751\/revisions"}],"predecessor-version":[{"id":9755,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9751\/revisions\/9755"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9751"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9751"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9751"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}