23.05.25 Today’s Leetcode

837. New 21 Game (medium)

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0 or n >= k + maxPts:
            return 1.0
        
        windowSum = 1.0
        probability = 0.0
        
        dp = [0.0] * (n + 1)
        dp[0] = 1.0
        
        for i in range(1, n + 1):
            dp[i] = windowSum / maxPts
            
            if i < k:
                windowSum += dp[i]
            else:
                probability += dp[i]
            
            if i >= maxPts:
                windowSum -= dp[i - maxPts]
        
        return probability

576. Out of Boundary Paths (medium)

lru_caching is great. when we use DFS, make to use hashable argumentsa and use lru_caching!

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        
        def out_of_boundary(p):
            return p[0] < 0 or p[0] >= m or p[1] < 0 or p[1] >= n

        MOD = 10**9 + 7

        @functools.lru_cache(None)
        def dfs(cur, move):
            if out_of_boundary(cur):
                return 1
            if move == 0:
                return 0

            temp = 0
            dirs = [1, 0, -1, 0, 1]
            for i in range(4):
                temp += dfs((cur[0] + dirs[i], cur[1] + dirs[i + 1]), move - 1)
            
            return temp % MOD

        return dfs((startRow, startColumn), maxMove)