【LeetCode】64. 最小路径和

0.总结

• 简单dp题

---

1.题目

2.思想

根据数据规模，可以看到本题需要使用dp
（1）dp[i][j] 表示到 坐标[i,j] 的最小路径和
（2）递推公式： dp[i][j] = min(dp[i][j-1],dp[i-1][j]) + grid[i][j]

3.代码

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:        
        m,n = len(grid),len(grid[0])
        # 补充最后一行 + 一列
        dp = [[9999 for i in range(n+1)] for j in range(m+1)]
        
        for i in range(m):
            for j in range(n): 
                if i == 0 and j == 0:
                    dp[0][0] = grid[0][0]
                    continue
                dp[i][j] = min(dp[i][j-1],dp[i-1][j]) + grid[i][j]
        # print(dp)
        return dp[m-1][n-1]