程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode Minimum Path Sum

LeetCode Minimum Path Sum

編輯:關於C++

LeetCode解題之Minimum Path Sum


原題

從一個矩陣的左上角出發到右下角,只能向右或向下走,找出哪一條路徑上的數字之和最小。

注意點:

所有數字都是非負的

例子:

輸入:
[
[1, 2, 4],
[2, 4, 1],
[3, 2, 1]
]

輸出: 9

解題思路

思路跟 Unique Paths 相似,不過從計算到達該點有多少種走法轉變為求最小和為多少。找出上面和左邊格子的最小值加上當前格子中的數字即可。為了節省空間,把二維dp降為一維的,因為是求最優解,前面的中間值可以拋棄。

AC源碼

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])

        dp = [0 for __ in range(n)]
        dp[0] = grid[0][0]
        for j in range(1, n):
            dp[j] = dp[j - 1] + grid[0][j]
        for i in range(1, m):
            dp[0] += grid[i][0]
            for j in range(1, n):
                dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]
        return dp[-1]


if __name__ == "__main__":
    assert Solution().minPathSum([
        [1, 2, 4],
        [2, 4, 1],
        [3, 2, 1]]) == 9
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved