题目
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]; } }
LeetCode | Minimum Path Sum,布布扣,bubuko.com
原文:http://blog.csdn.net/perfect8886/article/details/21413087