Re: [閒聊] 每日LeetCode

看板Marginalman作者Rushia (みけねこ的鼻屎)時間4月前 (2024/01/19 14:46)推噓2(2推 0噓 1→)

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

https://leetcode.com/problems/minimum-falling-path-sum/description 931. Minimum Falling Path Sum 給定一個 m*n 矩陣，你可以從最上面的格子走到底部格子，每次可往右下、左下、下，經過的數字和為Path Sum，求出走到底部的最小 Path Sum。 https://assets.leetcode.com/uploads/2021/11/03/failing1-grid.jpg

思路： 1.明顯動態規劃題，底部必定是從上面三格走過來的，所以我們只需要獲得上面三格的最小Sum就可以取得當前格子的最小，若 f(i, j) 表示座標 (i, j) 的最小 Path Sum ，則狀態轉移方程式： f(i, j) = MIN(f(i - 1, j - 1), f(i - 1, j), f(i - 1, j + 1)) + martrix(i, j) 2.因為只需要上面一層的結果所以可以把dp矩陣壓一壓，空間複雜度 O(m)。 Java Code： ---------------------------------------------- class Solution { public int minFallingPathSum(int[][] matrix) { int n = matrix.length; int m = matrix[0].length; int[] f = new int[m]; System.arraycopy(matrix[0], 0, f, 0, m); for (int i = 1; i < n; i++) { int prev = f[0]; for (int j = 0; j < m; j++) { int min = f[j]; if (j - 1 >= 0) { min = Math.min(min, prev); } if (j + 1 < m) { min = Math.min(min, f[j + 1]); } prev = f[j]; f[j] = min + matrix[i][j]; } } int res = Integer.MAX_VALUE; for (int i = 0; i < m; i++) { res = Math.min(res, f[i]); } return res; } } ---------------------------------------------- -- https://i.imgur.com/PIoxddO.jpg