Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/03/27 11:01)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串273/719 (看更多)

64. Minimum Path Sum 給定一個大小為 m x n 的矩陣，找到從最左上角到最右下角的一條路徑，使得路徑上所有元素的總和最小，路徑只能向下和向右移動。 Example： https://assets.leetcode.com/uploads/2020/11/05/minpath.jpg

Input: grid = [[1,3,1],[1,5,1],[4,2,1]] Output: 7 Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum. 思路： 1.任意一個點的總和必定是他的上面或左邊格子兩者最小路徑和加上當前元素，可以使用動態規劃在兩者之中取較小的，遍歷完整個陣列後就可以求得解。 Java Code： ---------------------------------------------- class Solution { public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; int[][] dp = new int[m][n]; dp[0][0] = grid[0][0]; for (int i = 1; i < m; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; } for (int i = 1; i < n; i++) { dp[0][i] = dp[0][i - 1] + grid[0][i]; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]); } } return dp[m - 1][n - 1]; } } ---------------------------------------------- 空間複雜度優化： 1.因為第i列只關心i-1列(正上方)的總和而不關心i-2列、i-3列、...所以我們只需要保存一維的成本矩陣，空間複雜度：O(nm) -> O(n) Java Code： ---------------------------------------------- class Solution { public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; int[] dp = new int[n]; dp[0] = grid[0][0]; for (int i = 1; i < n; i++) { dp[i] = dp[i - 1] + grid[0][i]; } for (int i = 1; i < m; i++) { dp[0] += grid[i][0]; for (int j = 1; j < n; j++) { dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]); } } return dp[n - 1]; } } ---------------------------------------------- https://i.imgur.com/acHi4CL.png