leetcode 中等难度 第64题 最小路径和-动态规划

简单的动态规划题，还没有前面两个难。

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

代码:

class Solution { public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length ; for(int i = 1 ; i < m ; i ++){//第一列变了 grid[i][0] += grid[i-1][0] ; } for(int j = 1 ; j < n ; j ++){//第一行变了 grid[0][j] += grid[0][j-1] ; } 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]; } }

空间复杂度：O(1),不需要额外的空间。