动态规划_leetcode.64.最小路径和

题目

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

说明：每次只能向下或者向右移动一步。

示例:

输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

分析

由于路径的方向只能是向下或向右，因此网格的第一行的每个元素只能从左上角元素开始向右移动到达，网格的第一列的每个元素只能从左上角元素开始向下移动到达，此时的路径是唯一的，因此每个元素对应的最小路径和即为对应的路径上的数字总和。

对于不在第一行和第一列的元素，可以从其上方相邻元素向下移动一步到达，或者从其左方相邻元素向右移动一步到达，元素对应的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值。由于每个元素对应的最小路径和与其相邻元素对应的最小路径和有关，因此可以使用动态规划求解。

状态定义：

• 设 dp为大小 m×n矩阵，其中 dp[i] [j]的值代表直到走到 (i,j)的最小路径和。

初始状态：

• dp[0][0] =grid[0][0]

算法流程

• 当i>0且j=0时，dp[i] [0]= dp[i - 1] [0]+ grid[i] [0].
• 当i=0且j> 0时，dp[0][j]= dp[0][j - 1]+ grid[0][ij]。
• 当i>0且j> 0时，dp[i[i] = min(dp[i - 1][j], dp[i[ji -1]) + gridi[j]。
• 后得到dp[m- 1][n - 1]的值即为从网格左上角到网格右下的最小
  路径和。

其实我们完全不需要建立 dp矩阵浪费额外空间，直接遍历 grid[i][j]修改即可。这是因为：grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j] ；原 grid矩阵元素中被覆盖为 dp 元素后（都处于当前遍历点的左上方），不会再被使用到。

复杂度分析

• 时间复杂度O(M×N) ： 遍历整个 grid 矩阵元素。

• 空间复杂度 O(1) ： 直接修改原矩阵，不使用额外空间。

	public int minPathSum(int[][] grid) {
		 if(grid == null || grid.length == 0 || grid[0].length == 0) {
			 return 0;
		 }
		 
		 int rows = grid.length, cols = grid[0].length;
		 int[][] dp = new int[rows][cols];
		 dp[0][0] = grid[0][0];
		 
		 for(int i = 0; i < rows; i++) {
			 for(int j = 0; j < cols; j++) {
				 if(i == 0 && j == 0) {
					 continue;
				 }else if(i == 0) {
					 dp[0][j] = dp[0][j - 1] + grid[0][j];
				 }else if(j == 0) {
					 dp[i][0] = dp[i - 1][0] + grid[i][0];
				 }else {
					 dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
				 }
			 }
		 }
		 
		 return dp[rows - 1][cols - 1];
	}

python

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return 0
        
        rows, columns = len(grid), len(grid[0])
        dp = [[0] * columns for _ in range(rows)]
        dp[0][0] = grid[0][0]
        for i in range(1, rows):
            dp[i][0] = dp[i - 1][0] + grid[i][0]
        for j in range(1, columns):
            dp[0][j] = dp[0][j - 1] + grid[0][j]
        for i in range(1, rows):
            for j in range(1, columns):
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        
        return dp[rows - 1][columns - 1]

不使用dp数组。直接原地修改

	public int minPathSum2(int[][] grid) {
		 if(grid == null || grid.length == 0 || grid[0].length == 0) {
			 return 0;
		 }
		 
		 int rows = grid.length, cols = grid[0].length;
		 
		 for(int i = 0; i < rows; i++) {
			 for(int j = 0; j < cols; j++) {
				 if(i == 0 && j == 0) {
					 continue;
				 }else if(i == 0) {
					 grid[0][j] = grid[0][j - 1] + grid[0][j];
				 }else if(j == 0) {
					 grid[i][0] = grid[i - 1][0] + grid[i][0];
				 }else {
					 grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
				 }
			 }
		 }
		 
		 return grid[rows - 1][cols - 1];
	}

python

class Solution:
    def minPathSum(self, grid: [[int]]) -> int:
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i == j == 0: continue
                elif i == 0:  grid[i][j] = grid[i][j - 1] + grid[i][j]
                elif j == 0:  grid[i][j] = grid[i - 1][j] + grid[i][j]
                else: grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
        return grid[-1][-1]

最后，不经历风雨,怎能在计算机的大山之顶看见彩虹呢！ 无论怎样，相信明天一定会更好！！！！！

本文地址：https://blog.csdn.net/weixin_45333934/article/details/107554791