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

看板Marginalman作者sustainer123 (caster )時間1年前 (2024/01/26 21:15)推噓5(5推 0噓 0→)

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

※ 引述《Rushia (みけねこ的鼻屎)》之銘言： : 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; : } : } : -------------------------------------------- Python3 Code: class Solution: def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int: moves = [(1,0),(0,1),(-1,0),(0,-1)] @cache def dfs(step,x,y): nonlocal moves,m,n if x < 0 or y < 0 or x == m or y == n: return 1 if step == 0: return 0 ans = 0 for a,b in moves: ans += dfs(step-1,x+a,y+b) ans %= 10**9+7 return ans return dfs(maxMove,startRow,startColumn) 思路差不多然後我又偷吃步對不起不過感覺有點懂dp了下次出dp題就不用偷吃步了 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.164.59 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1706274937.A.FE0.html

推

a9486l

01/26 21:15, 1年前 , 1^F

01/26 21:15, 1^F

推

SecondRun

01/26 21:24, 1年前 , 2^F

01/26 21:24, 2^F

推

ILoveErr

01/26 21:26, 1年前 , 3^F

01/26 21:26, 3^F