坐标型动态规划——最小路径和

Myth丶恋晨 2022-10-27 06:24 135阅读 0赞

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]

**示例：**

输入：grid = [[1,5,7,6,8],[4,5,4,4,9],[10,3,2,3,2]]
    输出：22
    解释：因为路径 1→4→7→7→3→3→2 的总和最小。

### 1、确定状态 ###

我们的最终目的是为了到达右下角，假设右下角坐标为(n-1,m-1)，因此最后一步要么(n-2,m-1)向下要么(n-1,m-2)向右。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 1]  
如果倒数第二步在（n-1,m-2)那么，前面一定是从（0，0）到（n-1，m-2）总和最小的路径。

如果倒数第二步在（n-2,m-1)那么，前面一定是从（0，0）到（n-2，m-1）总和最小的路径。

上面描述了最后一步和子问题则可以确定状态：f\[i\]\[j\]表示从(0,0)到（i，j)的路径最小数字总和

### 2、转移方程 ###

f\[i\]\[j\]表示从(0,0)到（i，j)的路径最小数字总和  
![在这里插入图片描述][20210203213820531.png]

### 3、初始条件和边界情况 ###

初始条件：f\[0\]\[0\]=A\[0\]\[0\]

边界情况：i=0或者j=0的时候只有一个方向能走

### 4、计算顺序 ###

一行一行的计算。答案是f\[n-1\]\[m-1\]  
时间复杂度：O(MN)；空间复杂度：O(MN)

### 5、代码实现 ###

class Solution(object):
        def minPathSum(self, grid):
            """ :type grid: List[List[int]] :rtype: int """
            dp = [[0]*len(grid[0]) for i in range(len(grid))]
            for i in range(1,len(grid)):
                for j in range(1,len(grid[0])):
                  if i==0 and j==0:
                    dp[i][i]==grid[i][j]
                    continue
                  t = float("inf")
                    if i>0:
                        t = min(t,dp[i-1][j])
                    if j>0:
                        t = min(t,dp[i][j-1])
                    dp[i][j] = t + grid[i][j]
            return dp[len(grid)-1][len(grid[0])-1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]: /images/20221024/24901996be9b434a8aa0c1998db27a65.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 1]: /images/20221024/531eeef13fb145fc98572c8b61419b5c.png
[20210203213820531.png]: /images/20221024/5f50f36cf3604a49bb0aeacb11352f03.png