[LintCode/LeetCode] Minimum Path Sum
文章目录
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.
You can only move either down or right at any point in time.
Note
遍历整个矩阵,对于dp[i][j],取上方dp[i-1][j]和左边dp[i][j-1]较小值,与grid[i][j]相加可得该点最小值。
Solution
public class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for (int i = 1; i < n; i++) {
dp[0][i] = dp[0][i-1] + grid[0][i];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[m-1][n-1];
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论