首页 > 代码库 > 【LeetCode】Minimum Path Sum 解题报告
【LeetCode】Minimum Path Sum 解题报告
【题目】
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.
【思路】求从左上角到右下角的最小路径值,典型的动态规划。
动规方程:dp[i][j] = grid[i][j] + min( dp[i-1][j], dp[i][j-1] );
时间复杂度为O(m*n),因为至少要遍历一遍二维表。
空间复杂度,如果用二维数组来存动规过程,那么就是O(m*n);但如果用一维数组来存动规过程,空间复杂度就为O(n)。
【Java代码】
public class Solution { // DP with two dimension table public int minPathSum1(int[][] grid) { int m = grid.length; int n = grid[0].length; int[][] ans = new int[m][n]; ans[0][0] = grid[0][0]; for (int i = 1; i < m; i++) { ans[i][0] = ans[i-1][0] + grid[i][0]; } for (int j = 1; j < n; j++) { ans[0][j] = ans[0][j-1] + grid[0][j]; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { ans[i][j] = Math.min(ans[i-1][j], ans[i][j-1]) + grid[i][j]; } } return ans[m-1][n-1]; } // DP with one dimension table public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; int[] ans = new int[n]; ans[0] = grid[0][0]; for (int j = 1; j < n; j++) { ans[j] = ans[j-1] + grid[0][j]; } for (int i = 1; i < m; i++) { ans[0] += grid[i][0]; for (int j = 1; j < n; j++) { ans[j] = Math.min(ans[j-1], ans[j]) + grid[i][j]; } } return ans[n-1]; } }
这道题非常典型,之前好像练过一道类似的,所以这次写的时候非常顺手。
【LeetCode】Minimum Path Sum 解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。