題目
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.
分析這題按題目意思一步一步做就是了,屬於不需要分析的動態規劃了,如果可以修改grid內元素,是不需要額外空間的。
代碼
public class MinimumPathSum { public int minPathSum(int[][] grid) { int M = grid.length; int N = grid[0].length; for (int j = 1; j < N; ++j) { grid[0][j] += grid[0][j - 1]; } for (int i = 1; i < M; ++i) { grid[i][0] += grid[i - 1][0]; } for (int i = 1; i < M; ++i) { for (int j = 1; j < N; ++j) { grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]); } } return grid[M - 1][N - 1]; } }