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.
You can only go right or down in the path..
Example
Example 1: Input: [[1,3,1],[1,5,1],[4,2,1]] Output: 7 Explanation: Path is: 1 -> 3 -> 1 -> 1 -> 1 Example 2: Input: [[1,3,2]] Output: 6 Explanation: Path is: 1 -> 3 -> 2
思路:Dp[i][j] 存储从(0, 0) 到(i, j)的最短路径。
Dp[i][j] = min(Dp[i-1][j]), Dp[i][j-1]) + grid[i][j];
public class Solution { /** * @param grid: a list of lists of integers * @return: An integer, minimizes the sum of all numbers along its path */ public int minPathSum(int[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; } int M = grid.length; int N = grid[0].length; int[][] sum = new int[M][N]; sum[0][0] = grid[0][0]; for (int i = 1; i < M; i++) { sum[i][0] = sum[i - 1][0] + grid[i][0]; } for (int i = 1; i < N; i++) { sum[0][i] = sum[0][i - 1] + grid[0][i]; } for (int i = 1; i < M; i++) { for (int j = 1; j < N; j++) { sum[i][j] = Math.min(sum[i - 1][j], sum[i][j - 1]) + grid[i][j]; } } return sum[M - 1][N - 1]; } }
可以使用滚动数组进行优化。
public class Solution { /** * @param grid: a list of lists of integers * @return: An integer, minimizes the sum of all numbers along its path */ public int minPathSum(int[][] A) { if (A == null || A.length == 0 || A[0].length == 0) { return 0; } int m = A.length, n = A[0].length; int[][] f = new int[2][n]; int i, j; int old, now = 0; // f[i] is stored in rolling array f[0] for (i = 0; i < m; ++i) { old = now; now = 1 - now; // 0 --> 1, 1 --> 0 for (j = 0; j < n; ++j) { if (i == 0 && j == 0) { f[now][j] = A[0][0]; continue; } f[now][j] = Integer.MAX_VALUE; if (i > 0) { f[now][j] = Math.min(f[now][j], f[old][j]); } if (j > 0) { f[now][j] = Math.min(f[now][j], f[now][j - 1]); } f[now][j] += A[i][j]; } } return f[now][n - 1]; } }