MinimumPathSum [source code]
public class MinimumPathSum {
static
/******************************************************************************/
class Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0)
return 0;
int R = grid.length, C = grid[0].length;
int[][] dp = new int[R][C];
for (int i = R - 1; i >= 0; i--) for (int j = C - 1; j >= 0; j--) {
if (i == R - 1 && j == C - 1)
dp[i][j] = grid[i][j];
else if (i == R - 1)
dp[i][j] = dp[i][j + 1] + grid[i][j];
else if (j == C - 1)
dp[i][j] = dp[i + 1][j] + grid[i][j];
else
dp[i][j] = Math.min (dp[i + 1][j], dp[i][j + 1]) + grid[i][j];
}
return dp[0][0];
}
}
/******************************************************************************/
public static void main(String[] args) {
MinimumPathSum.Solution tester = new MinimumPathSum.Solution();
}
}
又是一个右下移动, 那么肯定是一个DP问题了; 另外, 如果不是一个DP题目, 感觉可以用一个heap做法: 跟之前的SwimingInRisingWater有点类似; 不过这里的heap的weight应该是什么? 不对啊, 这不就是shortest path problem吗? 一个DJ算法就搞定了; 如果真的要定义weight, 那么heap里面每一个node的weight应该是length of the path so far to this node; 当然, 一个node可能实际上会被加到好几个state node里面; 但是因为是一个PriorityQueue算法, 所以不是穷搜, 最后不会导致速度有多大的损失: 较差的结果不到万不得已根本不会被考虑;
DP的话, 随便乱写写看看先; 另外, 写的过程中发现, 这题其实也是可以用InPlace的方法来写的, 不过没什么意思, 懒得搞了;
还是比较快的做完了, 速度是11ms (10%), 不知道为什么DP算法还是这么慢;
editorial
Approach #1 Brute Force [Time Limit Exceeded]
public class Solution {
public int calculate(int[][] grid, int i, int j) {
if (i == grid.length || j == grid[0].length) return Integer.MAX_VALUE;
if (i == grid.length - 1 && j == grid[0].length - 1) return grid[i][j];
return grid[i][j] + Math.min(calculate(grid, i + 1, j), calculate(grid, i, j + 1));
}
public int minPathSum(int[][] grid) {
return calculate(grid, 0, 0);
}
}
暴力DFS, 其实就是忘记加memo的Top-Down DP;
Approach #2 Dynamic Programming 2D [Accepted]
public class Solution {
public int minPathSum(int[][] grid) {
int[][] dp = new int[grid.length][grid[0].length];
for (int i = grid.length - 1; i >= 0; i--) {
for (int j = grid[0].length - 1; j >= 0; j--) {
if(i == grid.length - 1 && j != grid[0].length - 1)
dp[i][j] = grid[i][j] + dp[i][j + 1];
else if(j == grid[0].length - 1 && i != grid.length - 1)
dp[i][j] = grid[i][j] + dp[i + 1][j];
else if(j != grid[0].length - 1 && i != grid.length - 1)
dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
else
dp[i][j] = grid[i][j];
}
}
return dp[0][0];
}
}
Approach #3 Dynamic Programming 1D [Accepted]
public class Solution {
public int minPathSum(int[][] grid) {
int[] dp = new int[grid[0].length];
for (int i = grid.length - 1; i >= 0; i--) {
for (int j = grid[0].length - 1; j >= 0; j--) {
if(i == grid.length - 1 && j != grid[0].length - 1)
dp[j] = grid[i][j] + dp[j + 1];
else if(j == grid[0].length - 1 && i != grid.length - 1)
dp[j] = grid[i][j] + dp[j];
else if(j != grid[0].length - 1 && i != grid.length - 1)
dp[j] = grid[i][j] + Math.min(dp[j], dp[j + 1]);
else
dp[j] = grid[i][j];
}
}
return dp[0];
}
}
Approach #4 Dynamic Programming (Without Extra Space) [Accepted]
public class Solution {
public int minPathSum(int[][] grid) {
for (int i = grid.length - 1; i >= 0; i--) {
for (int j = grid[0].length - 1; j >= 0; j--) {
if(i == grid.length - 1 && j != grid[0].length - 1)
grid[i][j] = grid[i][j] + grid[i][j + 1];
else if(j == grid[0].length - 1 && i != grid.length - 1)
grid[i][j] = grid[i][j] + grid[i + 1][j];
else if(j != grid[0].length - 1 && i != grid.length - 1)
grid[i][j] = grid[i][j] + Math.min(grid[i + 1][j],grid[i][j + 1]);
}
}
return grid[0][0];
}
}
就这么回事儿吧, 没什么新意;
@jianchao.li.fighter said in 10-lines 28ms O(n)-space DP solution in C++ with Explanations:
This is a typical DP problem. Suppose the minimum path sum of arriving at point
(i, j)isS[i][j], then the state equation isS[i][j] = min(S[i - 1][j], S[i][j - 1]) + grid[i][j].Well, some boundary conditions need to be handled. The boundary conditions happen on the topmost row (
S[i - 1][j]does not exist) and the leftmost column (S[i][j - 1]does not exist). Supposegridis like[1, 1, 1, 1], then the minimum sum to arrive at each point is simply an accumulation of previous points and the result is[1, 2, 3, 4].Now we can write down the following (unoptimized) code.
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int> > sum(m, vector<int>(n, grid[0][0]));
for (int i = 1; i < m; i++)
sum[i][0] = sum[i - 1][0] + grid[i][0];
for (int j = 1; j < n; j++)
sum[0][j] = sum[0][j - 1] + grid[0][j];
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
sum[i][j] = min(sum[i - 1][j], sum[i][j - 1]) + grid[i][j];
return sum[m - 1][n - 1];
}
};
As can be seen, each time when we update
sum[i][j], we only needsum[i - 1][j](at the current column) andsum[i][j - 1](at the left column). So we need not maintain the fullm*nmatrix. Maintaining two columns is enough and now we have the following code.
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<int> pre(m, grid[0][0]);
vector<int> cur(m, 0);
for (int i = 1; i < m; i++)
pre[i] = pre[i - 1] + grid[i][0];
for (int j = 1; j < n; j++) {
cur[0] = pre[0] + grid[0][j];
for (int i = 1; i < m; i++)
cur[i] = min(cur[i - 1], pre[i]) + grid[i][j];
swap(pre, cur);
}
return pre[m - 1];
}
};
Further inspecting the above code, it can be seen that maintaining
preis for recoveringpre[i], which is simplycur[i]before its update. So it is enough to use only one vector. Now the space is further optimized and the code also gets shorter.
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<int> cur(m, grid[0][0]);
for (int i = 1; i < m; i++)
cur[i] = cur[i - 1] + grid[i][0];
for (int j = 1; j < n; j++) {
cur[0] += grid[0][j];
for (int i = 1; i < m; i++)
cur[i] = min(cur[i - 1], cur[i]) + grid[i][j];
}
return cur[m - 1];
}
};
看腻了, 这兄弟这三道DP题捞了好多upvote;
关于InPlace做法:
@weijiang2009 said in My java solution using DP and no extra space:
It is not sure whether we should modify the input. If permitted, that's good
真正面试的时候, 还是要问一下;
一般来说, 掌握O(N)空间的解法, 就没啥毛病了;
submission基本波动, recursion的好像稍微快一点:
class Solution {
public int minPathSum(int[][] grid) {
int[][] minSum = new int[grid.length][grid[0].length];
return helper(grid, 0, 0, minSum);
}
public int helper(int[][] grid, int i, int j, int[][] minSum) {
if (i == grid.length - 1 && j == grid[0].length - 1) return grid[i][j];
if (minSum[i][j] != 0) return minSum[i][j];
int down = Integer.MAX_VALUE, right = Integer.MAX_VALUE;
if (i < grid.length - 1) down = helper(grid, i + 1, j, minSum);
if (j < grid[0].length - 1) right = helper(grid, i, j + 1, minSum);
minSum[i][j] = Math.min(right, down) + grid[i][j];
return minSum[i][j];
}
}
Problem Description
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,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.
Difficulty:Medium
Total Accepted:138K
Total Submissions:344.4K
Contributor:LeetCode
Related Topics
arraydynamic programming
Similar Questions
Unique PathsDungeon GameCherry Pickup