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

看板Marginalman作者Rushia (みけねこ的鼻屎)時間1年前 (2024/01/26 15:48)推噓2(2推 0噓 1→)

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

576. Out of Boundary Paths 給你一些數字 m = 列數, n = 行數, maxMove = 移動步數, startRow 和 startColumn為矩陣的出發座標，求出移動 1~maxMove 步後共有幾種結果會走出矩陣外外，因為數字很大要取MOD。 1.模擬從起始座標往四個方向前進，如果出界就把res+1 否則繼續往四個方向不斷dfs，直到沒步數或出界。 2.直接跑會TLE，因為在走的過程中可能會走到已經算過的點，所以可以用memo記憶化搜索，dp[i][j][k] 表示當前位置最多使用 k 步會走出去的路徑數量。 Java Code: -------------------------------------------- class Solution { private int m, n; private Integer[][][] cache; private int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) { this.m = m; this.n = n; cache = new Integer[m][n][maxMove + 1]; return dfs(startRow, startColumn, maxMove); } private int dfs(int y, int x, int step) { if (y < 0 || x < 0 || y == m || x == n) { return 1; } if (step == 0) { return 0; } if (cache[y][x][step] != null) { return cache[y][x][step]; } int ans = 0; for (int[] dir : dirs) { ans += dfs(y + dir[0], x + dir[1], step - 1); ans %= 1e9+7; } return cache[y][x][step] = ans; } } -------------------------------------------- -- https://i.imgur.com/PIoxddO.jpg