LeetCode 5270. Minimum path cost in grid (dynamic programming)

List of articles

• 1. subject
• 2. Problem solving

1. subject

I'll give you a subscript from 0 The starting integer matrix grid , The matrix size is m x n , From 0 To m * n - 1 Is composed of different integers . You can use this matrix , Move from a cell to The next line Any other cell of the . If you are in a cell (x, y) , And meet x < m - 1 , You can move to (x + 1, 0), (x + 1, 1), ..., (x + 1, n - 1) Any cell in the . Be careful ： Cells in the last row cannot trigger a move .

Every possible move comes at a corresponding cost , The price is from with a subscript 0 Start with a two-dimensional array moveCost Express , The array size is (m * n) x n , among moveCost[i][j] It's from The value is i The cell of moves to the next row j Column The cost of cells . from grid The cost of cell movement in the last row can be ignored .

grid The cost of a path is ： Of all cells the path passes through Sum of values add All mobile Sum of costs . from first line Start from any cell , Return to The last line Of any cell Minimum Path cost .

Example 1：

 Input ：grid = [[5,3],[4,0],[2,1]], 
moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
 Output ：17
 explain ： The path with the least cost is  5 -> 0 -> 1 .
-  The path passes through the sum of cell values  5 + 0 + 1 = 6 .
-  from  5  Move to  0  The price is  3 .
-  from  0  Move to  1  The price is  8 .
 The total cost of the path is  6 + 3 + 8 = 17 .
 Example  2：

 Input ：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]]
 Output ：6
 explain ：
 The path with the least cost is  2 -> 3 . 
-  The path passes through the sum of cell values  2 + 3 = 5 . 
-  from  2  Move to  3  The price is  1 . 
 The total cost of the path is  5 + 1 = 6 .
 
 Tips ：
m == grid.length
n == grid[i].length
2 <= m, n <= 50
grid  From  0  To  m * n - 1  Is composed of different integers 
moveCost.length == m * n
moveCost[i].length == n
1 <= moveCost[i][j] <= 100

Copy

source ： Power button （LeetCode） link ：https://leetcode.cn/problems/minimum-path-cost-in-a-grid Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

2. Problem solving

• dp[i][j] Indicates arrival (i, j) The minimum cost of time

class Solution {
public:
    int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
        for(int j = 0; j < n; ++j)
            dp[0][j] = grid[0][j];
        for(int i = 1; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                for(int k = 0; k < n; ++k)
                {
                    dp[i][j] = min(dp[i][j], dp[i-1][k]+moveCost[grid[i-1][k]][j]+grid[i][j]);
                }
            }
        }
        return *min_element(dp.back().begin(), dp.back().end());
    }
};

Copy

272 ms 78.5 MB C++

---

my CSDN Blog address https://michael.blog.csdn.net/