Problem:
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example 1:
|
1 2 3 |
[[1,3,1], [1,5,1], [4,2,1]] |
Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.
Idea:
DP
Solution 1:
C++ / Recursion with memoization
Time complexity: O(mn)
Space complexity: O(mn)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua // Runtime: 9 ms class Solution { public: int minPathSum(vector<vector<int>>& grid) { int m = grid.size(); if (m == 0) return 0; int n = grid[0].size(); s_ = vector<vector<int>>(m, vector<int>(n, 0)); return minPathSum(grid, n - 1, m - 1, n, m); } private: long minPathSum(const vector<vector<int>>& grid, int x, int y, int n, int m) { if (x == 0 && y == 0) return grid[y][x]; if (x < 0 || y < 0) return INT_MAX; if (s_[y][x] > 0) return s_[y][x]; int ans = grid[y][x] + min(minPathSum(grid, x - 1, y, n, m), minPathSum(grid, x, y - 1, n, m)); return s_[y][x] = ans; } vector<vector<int>> s_; }; |
Solution 2:
C++ / DP
Time complexity: O(mn)
Space complexity: O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua // Runtime: 9 ms class Solution { public: int minPathSum(vector<vector<int>>& grid) { int m = grid.size(); if (m == 0) return 0; int n = grid[0].size(); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { if (i == 0 && j == 0) continue; if (i == 0) grid[i][j] += grid[i][j - 1]; else if (j == 0) grid[i][j] += grid[i - 1][j]; else grid[i][j] += min(grid[i][j - 1], grid[i - 1][j]); } return grid[m - 1][n - 1]; } }; |
Related Problems: