BFS

1293. Shortest Path in a Grid with Obstacles Elimination

Using location and number of eliminate to encode the states is critical.

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        R, C = len(grid), len(grid[0])
        if (R-1,C-1)==(0,0) and k>=grid[0][0]:return 0
        def bfs():
            que = collections.deque([(0, 0,0, grid[0][0])])
            seen = {(0, 0, grid[0][0])}
            while que:
                i, j, d, eliminate = que.popleft()
                for di, dj in [(0, 1),(0,-1),(1,0),(-1,0)]:
                    r, c = i+di, j+dj
                    if 0<=r<R and 0<=c<C and (r, c, eliminate+grid[r][c]) not in seen:
                        if (r,c)==(R-1, C-1):return d+1
                        new_eliminate = eliminate + grid[r][c]
                        seen.add((r,c,new_eliminate))
                        if new_eliminate<=k:
                            que.append((r,c,d+1,new_eliminate))
            return -1
        return bfs()

818. Race Car

https://leetcode.com/problems/race-car/

A nice summary can be found here

Summary of the BFS and DP solutions with intuitive explanation - LeetCode Discuss

BFS

Runtime: 3020 ms, faster than 23.89% of Python3 online submissions for Race Car.

Memory Usage: 326 MB, less than 100.00% of Python3 online submissions for Race Car.

class Solution:
    def racecar(self, target: int) -> int:
        def bfs():
            from collections import deque
            Q = deque([(0,1,0)])
            seen = {(0,1)}
            if target==0:return 0
            while True:
                p, s, d = Q.popleft()
                if p==target:return d
                for action in [True, False]:
                    if action:
                        this_p = p+s
                        s*=2
                        if this_p==target:return d+1
                        if (this_p, s) not in seen:
                            seen.add((this_p, s))
                            Q.append((this_p, s,d+1))
                    else:
                        if s>0:s=-1
                        else:s=1
                        if (p,s) not in seen:
                            seen.add((p, s))
                            Q.append((p, s,d+1))
        
        return bfs()

If we change it to DP as shown here:

We get a much faster speed:

Runtime: 52 ms, faster than 93.36% of Python3 online submissions for Race Car.

Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Race Car.

class Solution:
    def __init__(self): 
        self.dp = {0: 0}
        
    def racecar(self, t: int) -> int:
        if t in self.dp: return self.dp[t]
        n = t.bit_length()
        if 2**n - 1 == t: self.dp[t] = n
        else:
            self.dp[t] = self.racecar(2**n - 1 - t) + n + 1
            for m in range(n - 1):
                self.dp[t] = min(self.dp[t], self.racecar(t - 2**(n - 1) + 2**m) + n + m + 1)
        return self.dp[t]