dfs(i) = dfs(i+1) + dfs(i+2)

    Top-Down:    n
                / \
            n-1  n-2
            / \   ...
            ...

    computed recursively

            
    Bottom-Up: 0 1 2 3 ... n
    
    computed iteratively

    def rob(self, nums: List[int]) -> int:

        n = len(nums)

        # Edge case: only 1 house
        # Without this, accessing nums[1] would cause IndexError
        if n == 1:
            return nums[0]

        # dp[i] = max money robbed from houses 0..i
        # Rule (2): "element i itself"
        dp = [0] * n                  # direct:
        dp[0] = nums[0]               # direct: max loop up to ith house
        dp[1] = max(nums[0], nums[1]) # direct: max loop up to 2nd house

        for i in range(2, n):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])

        return dp[n-1]

    def rob(nums: List[int]) -> int:

        n = len(nums)

        # dp[i] = max money robbed from the first i houses
        # Rule (1): "the first i elements"
        dp = [0] * (n+1)  # padding:
        dp[0] = 0         # padding: (empty case, max loot from no houses)
        dp[1] = nums[0]

        for i in range(2, n+1):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])

        return dp[n]

    def climbStairs(n: int) -> int:

        # dp[i] = ways to reach step i
        # Rule (1): "the first i elements"
        dp = [0] * (n+1)  # padding:
        dp[0] = 1         # padding: (ground case, 1 way: do nothing)
        dp[1] = 1 

        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]

        return dp[n]

    def climbStairs(n: int) -> int:
        
        # Edge cases:
        # Without this, setting dp[1] would cause IndexError
        if n == 1:
            return 1

        # dp[i] = ways to reach step (i+1)
        # Rule (2): "element i itself"
        dp = [0] * n  # direct
        dp[0] = 1     # direct: (ways to reach step 1)
        dp[1] = 2     # direct: (ways to reach step 2)

        for i in range(2, n):
            dp[i] = dp[i-1] + dp[i-2]

        return dp[n-1]

    def climbStairs(n: int) -> int:

        memo = {}

        def dfs(i: int) -> int:

            if i in memo:
                return memo[i]

            if i == 0:  # padding: ground, 1 way to do nothing
                return 1
            if i == 1:  # padded: first step
                return 1

            # recursive relation: sum of previous two steps
            memo[i] = dfs(i-1) + dfs(i-2)
            return memo[i]

        return dfs(n)

    def climbStairs(n: int) -> int:
        
        memo = {}

        def dfs(i: int) -> int:

            if i in memo:
                return memo[i]

            if i == 1:   # direct: 1st element
                return 1
            if i == 2:   # direct: 2nd element
                return 2

            # recursive relation: sum of previous two steps
            memo[i] = dfs(i-1) + dfs(i-2)
            return memo[i]

        return dfs(n)

    def climbStairs(n: int):

        # no length == 1 check, since using pad + 1st element
        # 1st element will always exist, pad is made up

        dp = [0] * (n + 1)  # padding:
        dp[0] = 1           # padding: (ground, 1 way to do nothing), 
                            # does not exist in original array

        dp[1] = 1           # padded: first element, n=0 -> dp[1]

        for i in range(2, n + 1):
            dp[i] = dp[i-1] + dp[i-2]

        return dp[n]

    def rob(nums):
        n = len(nums)

        # length == 1 check needed since using 1st + 2nd element
        # 2nd element may not exist
        if n == 1:
            return nums[0]

        dp = [0] * n                   # direct:
        dp[0] = nums[0]                # direct: 1st element
        dp[1] = max(nums[0], nums[1])  # direct: 2nd element

        for i in range(2, n):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])

        return dp[n-1]

    def climbStairs(n: int) -> int:

        # no length == 1 check, since using pad + 1st element
        # 1st element will always exist, pad is made up

        # padded variables
        prev2 = 1  # padding: ground (0 steps, 1 way to do nothing)
        prev1 = 1  # first step

        # no length check needed since prev1 and prev2 already cover n=1
        for i in range(2, n + 1):
            curr = prev1 + prev2
            prev2, prev1 = prev1, curr

        return prev1

    def rob(nums) -> int:
        n = len(nums)
        
        # length == 1 check needed since using 1st + 2nd element
        # 2nd element may not exist
        if n == 1:
            return nums[0]

        prev2 = nums[0]                # direct: first element
        prev1 = max(nums[0], nums[1])  # direct: second element

        for i in range(2, n):
            curr = max(prev1, prev2 + nums[i])
            prev2, prev1 = prev1, curr

        return prev1

    def maxProduct(nums: List[int]) -> int:
        n = len(nums)
        
        # Direct Variables -> rolling left and right products
        left_prod = right_prod = 1
        res = float('-inf')

        for i in range(n):
            # Build From Previous -> roll from left and right ends
            left_prod *= nums[i]
            right_prod *= nums[n-1-i]

            # Three Possibilities -> compare overall max
            res = max(res, left_prod, right_prod)

            # Direct Boundary -> reset rolling on zero
            if left_prod == 0:
                left_prod = 1
            if right_prod == 0:
                right_prod = 1

        return res

    def wordBreak(s: str, wordDict: List[str]) -> bool:
        n = len(s)
        
        # Direct Length -> empty string check
        if n == 0:
            return True

        word_set = set(wordDict)
        max_len = max(map(len, wordDict)) if wordDict else 0

        # Direct Variables -> initialize rolling DP window
        dp = [False] * (max_len + 1)
        dp[0] = True  # base case: empty string

        # Iterate -> 1 to n
        for i in range(1, n + 1):
            dp[i % (max_len + 1)] = False

            # Build From Previous -> look back up to max_len positions
            for l in range(1, min(i, max_len) + 1):
                # Three Possibilities -> valid segmentation from previous l positions
                if dp[(i - l) % (max_len + 1)] and s[i - l:i] in word_set:
                    dp[i % (max_len + 1)] = True
                    break  # early stop, valid segmentation found

        # Result -> final DP state
        return dp[n % (max_len + 1)]

    def coinChange(coins, amount):
        if amount == 0:
            return 0

        # Queue stores (remaining amount, coins used so far)
        queue = deque([(amount, 0)])
        visited = set([amount])  # memo: avoid revisiting same remaining amount

        while queue:
            rem, steps = queue.popleft()

            # Explore choices
            for coin in coins:
                next_rem = rem - coin

                # Early stop: minimal coins found
                if next_rem == 0:
                    return steps + 1

                # Valid state & not visited
                if next_rem > 0 and next_rem not in visited:
                    visited.add(next_rem)
                    queue.append((next_rem, steps + 1))

        # Impossible to reach target
        return -1

  oh! pseudocode hasn't been written yet, try another card! :)

    def climbStairs(self, n: int) -> int:

        # BFS Over The Implicit "Step" Graph
        #   - each step from 0 to n is a node in an implicit graph, no
        #     literal graph is built up front
        #   - an edge connects step i to step i+1 and step i+2, since
        #     taking 1 or 2 steps from i are the only legal moves forward

        # Note:
        # Unlike a typical "shortest path" BFS (e.g. Perfect Squares),
        # here we don't want the FIRST time n is reached -- we want the
        # TOTAL number of distinct paths from 0 to n. So instead of
        # returning early at the first dequeue of n, we propagate a
        # "ways" count forward across every edge and let the queue fully
        # drain, similar to a topological-order path-counting traversal.

        # BFS State Encoding:
        #   - each queued item is simply a step index i
        #   - ways[i] tracks how many distinct paths from 0 have reached
        #     step i so far, accumulated as new edges into i are processed

        # Legal Next Moves:
        #   - From step i, moving to i+1 or i+2 is legal as long as it
        #     doesn't overshoot n

        # Discovery vs. Accumulation:
        #   - A step is enqueued only the FIRST time it's discovered
        #     (standard BFS visited-set behavior), to avoid processing
        #     the same node's own outgoing edges more than once
        #   - But ways[step] keeps ACCUMULATING every time an edge into
        #     it is processed, even after it's already been enqueued --
        #     this is what correctly sums contributions from both i-1
        #     and i-2 reaching the same step

        # Safety Insight:
        # because edges only ever point to LARGER indices (i+1, i+2),
        # a step's predecessors (i-1, i-2) are always discovered and
        # enqueued no later than the step itself, so by the time a step
        # is dequeued, all paths reaching it have already been added to
        # its ways count

        # Edge Case:
        # n = 0 -- vacuously 1 way to "reach" the top (no steps needed)
        if n == 0:
            return 1

        # Ways Array:
        # ways[i] = number of distinct paths from step 0 to step i
        # sc: O(n)
        ways = [0] * (n + 1)
        ways[0] = 1

        # Iterative BFS Queue:
        #   - seed the queue with the starting step, 0
        queue = deque([0])

        # Self Edges and Parallel Edges Safety Tracking:
        #   - mark starting step as visited (discovered), so its
        #     outgoing edges are only ever processed once
        # sc: O(n)
        visited = {0}

        # tc: O(n), each step dequeued and expanded exactly once
        while queue:

            i = queue.popleft()

            # Explore Neighbors:
            #   - move forward by 1 step and by 2 steps
            for move in (1, 2):

                j = i + move

                # Legal Move Check:
                #   - skip any move that overshoots the top
                if j > n:
                    continue

                # Accumulate:
                #   - every path reaching i also reaches j via this edge,
                #     so add i's path count onto j's
                # tc: O(1)
                ways[j] += ways[i]

                # Discovery Check:
                #   - only enqueue j the first time it's discovered, so
                #     its own outgoing edges are expanded exactly once
                if j not in visited:
                    visited.add(j)
                    queue.append(j)

        # Result:
        # ways[n] holds the total number of distinct paths from 0 to n,
        # accumulated across every edge that ever pointed into it
        res = ways[n]

        # overall: tc O(n) -- each of the n+1 steps is dequeued once,
        # expanding at most 2 edges
        # overall: sc O(n) -- ways array, visited set, and queue
        return res

    def climbStairs(self, n: int) -> int:

        # Dynamic Programming (DP):
        # DP is used when a problem has:
        #   1. Overlapping subproblems
        #   2. Optimal substructure
        # Instead of recomputing subproblems, we cache results and compute 
        # each subproblem only once.

        # Three DP Perspectives:
        # 1. i -> N (Top-Down Recursive with Memoization)
        # 2. 0 -> i (Bottom-Up Recursive)
        # 3. 0 -> i (Bottom-Up Iterative / Tabulation)
        # This solution uses 0 -> i (Top-Down Recursive with Memoization)

        # State Definition:
        # Let dfs(i) represent the number of ways to reach step i
        # starting from step 0.

        # Recurrence Relation:
        # To reach step i, you can come from:
        #   - step i-1 (1 step)
        #   - step i-2 (2 steps)
        # Therefore:
        #   dfs(i) = dfs(i - 1) + dfs(i - 2)

        # Base Cases (Padded Boundaries):
        #   - If i == 0: ground level -> 1 valid way
        #   - If i == 1: first step -> 1 valid way
        # Padding eliminates the need for explicit length checks.

        # Memoization (Caching Overlapping Subproblems):
        # Multiple paths can reach the same step i.
        # Without caching, recursion becomes exponential.
        # With memoization, each state i is computed once.
        # Ways to climb from 0 to ith step

        # sc: O(n) for memo dictionary
        memo = {}

        def dfs(i):

            # Memo Check:
            # Check: if step has been computed previously
            # tc: O(1)
            if i in memo:
                return memo[i]
            
            # Base Case: Ground Level
            # i == 0, 1 way to reach ground level
            # tc: O(1)
            if i == 0:
                return 1

            # Base Case: First Step
            # i == 1, 1 way to reach first step
            # tc: O(1)
            if i == 1:
                return 1

            # Recurrence Relation:
            # Build from previous states: step i-1 and i-2
            # dfs(i) = dfs(i - 1) + dfs(i - 2)
            # tc: O(1) per call, overall O(n) due to memoization
            memo[i] = dfs(i - 1) + dfs(i - 2)

            # Return:
            # Number of ways to reach step i
            # tc: O(1)
            return memo[i]

        # Initial Call:
        # Number of ways to reach step n
        # tc: O(1)
        res = dfs(n)

        # overall: tc O(n)
        # overall: sc O(n)
        return res

    def climbStairs(self, n: int) -> int:
        
        # Dynamic Programming (DP):
        # DP is used when a problem has:
        #   1. Overlapping subproblems
        #   2. Optimal substructure
        # Bottom-Up DP can be optimized to use constant space by only
        # storing the last two computed states, since each state depends
        # only on the previous two.
        
        # Three DP Perspectives:
        # 1. i -> N (Top-Down Recursive with Memoization)
        # 2. 0 -> i (Top-Down Recursive / 0 → i)
        # 3. 0 → i (Bottom-Up Iterative / Tabulation)
        # This solution uses 0 → i (Bottom-Up Iterative with Rolling Variables)

        # State Definition:
        # prev2: number of ways to reach step i-2
        # prev1: number of ways to reach step i-1
        # curr: number of ways to reach step i
        # Only two previous states are needed because dp[i] = dp[i-1] + dp[i-2]


        # State Definition:
        # prev2: step i-2
        # prev1: step i-1
        # curr:  step i
        # Only two previous states are needed because dp[i] = dp[i-1] + dp[i-2]
        # sc: O(1)
        TwoPrev = 1  # ground
        OnePrev = 1  # first step

        # Iterative Build (Bottom-Up Traversal):
        # Start from [2, n]
        # For each step i, build current number of ways from previous two
        # tc: O(1) per iteration, overall O(n)
        for i in range(2, n+1):

            # Build From Previous:
            # Number of ways to reach step i is sum of ways to reach previous two steps
            curr = TwoPrev + OnePrev

            # Roll Variable:
            # Move values forward
            TwoPrev, OnePrev = OnePrev, curr
        
        # Result:
        # Number of ways to reach step n
        # tc: O(1)
        res = OnePrev

        # overall: tc O(n)
        # overall: sc O(1)
        return res

  oh! pseudocode hasn't been written yet, try another card! :)

    def minCostClimbingStairs(self, cost: List[int]) -> int:

        # BFS Over The Implicit "Step" Graph
        #   - each step from 0 to n (n = top, one past the last index) is
        #     an implicit node, no literal graph is built up front
        #   - an edge connects step i to step i+1 and step i+2, weighted
        #     by cost[i] -- the price paid to LEAVE step i toward either
        #     neighbor

        # Note:
        # Unlike Climbing Stairs' BFS (path counting) or Perfect Squares'
        # BFS (first-arrival shortest path), this is a WEIGHTED graph, so
        # plain unweighted BFS doesn't directly give minimum cost. What
        # makes BFS still valid here is that every edge points to a
        # STRICTLY LARGER index (i -> i+1, i -> i+2), so the graph is a
        # DAG with a natural topological order = increasing step index.
        # Processing nodes via a FIFO queue in discovery order happens to
        # match that topological order, so relaxing edges as we dequeue
        # each node still guarantees dist[i] is finalized (never improved
        # again) by the time i is dequeued -- same idea as DAG shortest
        # path via topological relaxation.

        # BFS State Encoding:
        #   - each queued item is simply a step index i
        #   - dist[i] tracks the minimum cost accumulated to ARRIVE at
        #     step i so far, relaxed (improved) every time an edge into
        #     it is processed

        # Legal Next Moves:
        #   - From step i, moving to i+1 or i+2 is legal as long as it
        #     doesn't overshoot n (the top, one past the last step)

        # Discovery vs. Relaxation:
        #   - A step is enqueued only the FIRST time it's discovered, to
        #     avoid expanding the same node's outgoing edges more than once
        #   - But dist[step] keeps getting RELAXED (min'd) every time a
        #     new edge into it is processed, even after it's enqueued --
        #     this correctly captures the cheaper of the two incoming
        #     paths (from i-1 or from i-2)

        # Safety Insight:
        # because edges only ever point to LARGER indices, a step's
        # predecessors (i-1, i-2) are always discovered and enqueued no
        # later than the step itself, so by the time a step is dequeued,
        # both possible incoming edges have already relaxed its dist

        n = len(cost)

        # Dist Array:
        # dist[i] = min cost to arrive at step i
        # dist[n] represents arriving at the top, one past the last step
        # sc: O(n)
        dist = [float('inf')] * (n + 1)

        # Free Starting Steps:
        # you may start at step 0 or step 1 at no entry cost
        dist[0] = 0
        dist[1] = 0

        # Iterative BFS Queue:
        #   - seed the queue with both valid starting steps
        queue = deque([0, 1])

        # Self Edges and Parallel Edges Safety Tracking:
        #   - mark both starting steps as visited (discovered), so their
        #     outgoing edges are only ever processed once
        # sc: O(n)
        visited = {0, 1}

        # tc: O(n), each step dequeued and expanded exactly once
        while queue:

            i = queue.popleft()

            # Explore Neighbors:
            #   - move forward by 1 step and by 2 steps, paying cost[i]
            #     to leave step i
            for move in (1, 2):

                j = i + move

                # Legal Move Check:
                #   - skip any move that overshoots the top
                if j > n:
                    continue

                # Relax:
                #   - arriving at j via i costs dist[i] + cost[i]; keep
                #     the cheaper of that vs. whatever j already has
                # tc: O(1)
                candidate = dist[i] + cost[i]
                if candidate < dist[j]:
                    dist[j] = candidate

                # Discovery Check:
                #   - only enqueue j the first time it's discovered, so
                #     its own outgoing edges are expanded exactly once
                if j not in visited:
                    visited.add(j)
                    queue.append(j)

        # Result:
        # dist[n] holds the minimum cost to reach the top, having
        # relaxed every edge that ever pointed into it
        res = dist[n]

        # overall: tc O(n) -- each of the n+1 steps is dequeued once,
        # expanding at most 2 edges
        # overall: sc O(n) -- dist array, visited set, and queue
        return res

    def minCostClimbingStairs(self, cost: List[int]) -> int:
        
        # Note:
        # Top Down DP (memoized recursion)
        # 0. Direct Length -> no need for len == 1 check, recursive direct boundary covers it
        # 1. Memo Check -> computed previously
        # 2. Direct Boundary -> 1st element
        # 3. Direct Boundary -> 2nd element
        # 4. Direct Build From Previous -> grab from previous two steps and sum paths
        # 5. Memo return -> return ways, calculated once
        # Result: min cost to reach n from last or 2nd to last step

        n = len(cost)

        memo = {}

        def dfs(i):

            # Memo Check -> computed previously
            if i in memo:
                return memo[i]

            # Direct Boundary -> 1st element
            if i == 0:
                return cost[0]

            # Direct Boundary -> 2nd element
            if i == 1:
                return cost[1]

            # Build -> min cost to reach + cost to continue
            memo[i] = cost[i] + min(dfs(i-1), dfs(i-2))
            return memo[i]

        # res -> reach n by continuing from nth or nth-1 step (since we step 1 or 2 steps)
        res = min(dfs(n-1), dfs(n-2))

        # overall: time complexity O(n)
        # overall: space complexity O(n) (memo + recursive stack)
        return res

    def minCostClimbingStairs(self, cost: List[int]) -> int:
        
        # Note:
        # Bottom Up Variables
        # 0. Direct Length -> no need for len == 1 check, description says min length == 2
        # 1. Direct Variables -> 1st + 2nd element
        # 2. Iterate -> 2 to n-1
        # 3. Build From Previous -> grab from previous two steps and sum paths
        # 3. Roll Variables -> Iterate Variables
        # Result: min cost to reach n via continuing from last or 2nd to last step (n-1, or n-2)

        # 0. Direct Length -> no need for len == 1 check, description says min length == 2

        n = len(cost)

        # Direct Variables -> 1st + 2nd element
        prev2, prev1 = cost[0], cost[1]

        # Iterate -> 2 to n-1
        for i in range(2, n):
            
            # Build From Previous -> grab from previous two steps and sum paths
            curr = cost[i] + min(prev1, prev2)

            # Roll Variables -> Iterate Variables
            prev2, prev1 = prev1, curr

        # res -> min cost to reach n
        res = min(prev1, prev2)

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return res

  oh! pseudocode hasn't been written yet, try another card! :)

    def tribonacci(self, n: int) -> int:

        # BFS Over The Implicit "Index" Graph
        #   - each index from 0 to n is an implicit node, no literal
        #     graph is built up front
        #   - an edge connects index i to index i+1, i+2, and i+3, since
        #     T(i) contributes to each of those three future sums

        # Note:
        # T0, T1, T2 are fixed BASE CASES, not sums built from earlier
        # values -- they must never receive propagated contributions from
        # each other. Only indices >= 3 are actually defined by the
        # recurrence, so propagation is only allowed to land on j >= 3.
        # Without this guard, node 0's outgoing edge into node 2 (and
        # node 1's edge into node 2) incorrectly adds onto T2's seeded
        # value before it's ever used, corrupting every downstream sum.

        if n == 0:
            return 0
        if n == 1:
            return 1
        if n == 2:
            return 1

        # sc: O(n)
        value = [0] * (n + 1)
        value[0] = 0
        value[1] = 1
        value[2] = 1

        queue = deque([0, 1, 2])

        # sc: O(n)
        visited = {0, 1, 2}

        # tc: O(n), each index dequeued and expanded exactly once
        while queue:

            i = queue.popleft()

            for move in (1, 2, 3):

                j = i + move

                # Legal Move Check:
                #   - skip overshoot past n
                #   - skip landing on a fixed base index (0, 1, 2), since
                #     those are seeded directly, never accumulated into
                if j > n or j < 3:
                    continue

                value[j] += value[i]

                if j not in visited:
                    visited.add(j)
                    queue.append(j)

        res = value[n]

        # overall: tc O(n)
        # overall: sc O(n)
        return res

    def tribonacci(self, n: int) -> int:

        # Note:
        # Top Down DP (memoized recursion)
        # 1. Memo Check -> computed previously
        # 2. Direct Boundary -> 1st element
        # 3. Direct Boundary -> 2nd element
        # 4. Direct Boundary -> 3rd element
        # 5. Build From Previous -> grab from previous two steps and sum paths
        # 6. Memo return -> return ways, calculated once
        # Result: T_i in Tribonacci sequence

        memo = {}

        def dfs(i):

            # Memo Check -> computed previously
            if i in memo:
                return memo[i]

            # Boundary -> 1st element
            if i == 0:
                return 0
            # Boundary -> 2nd element
            if i == 1:
                return 1
            # Boundary -> 3rd element
            if i == 2:
                return 1

            # Build From Previous -> grab from previous two steps and sum paths
            memo[i] = dfs(i-1) + dfs(i-2) + dfs(i-3)
            return memo[i]

        # res -> T_n value
        res = dfs(n)

        # overall: time complexity O(n)
        # overall: space complexity O(n) (memo + recursion stack)
        return res

    def tribonacci(self, n: int) -> int:

        # Note:
        # this is a unique case where Direct/N, requires an array of (N+1)
        # since we have 0 -> N fib solutions

        # Note:
        # Iterative Bottom Up Variables
        # 1. Direct Boundary -> need len == 1 check, elements 2 and 3 may not exist
        # 2. Direct Variables -> 1st + 2nd + 3rd elements
        # 3. Iterate -> 3 to n
        # 4. Build From Previous -> grab from previous two steps and sum paths
        # 5. Roll Variables -> Iterate Variables
        # Result: T_n in Tribonacci sequence

        # Direct Boundary -> need len == 1 check, elements 2 and 3 may not exist
        if n == 0:
            return 0
        if n == 1:
            return 1 

        # Direct Variables -> 1st + 2nd + 3rd elements
        ThreePrev, TwoPrev, OnePrev = 0, 1, 1

        # Iterate -> 3 to n
        for i in range(3, n+1):

            # Build From Previous -> grab from previous two steps and sum paths
            curr = ThreePrev + TwoPrev + OnePrev

            # Roll Variables -> Iterate Variables
            ThreePrev, TwoPrev, OnePrev = TwoPrev, OnePrev, curr

        # res -> nth tribonacci
        res = OnePrev

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return res

  oh! pseudocode hasn't been written yet, try another card! :)

    def generate(self, numRows: int) -> List[List[int]]:

        # BFS Over The Implicit "Position" Graph
        #   - each cell (row, col) in the triangle is an implicit node,
        #     no literal graph is built up front
        #   - an edge connects (row, col) to (row+1, col) and to
        #     (row+1, col+1), since each value contributes to the TWO
        #     values directly below it in the next row

        # Note:
        # Unlike the earlier BFS solutions (Climbing Stairs, Tribonacci)
        # where BFS levels didn't naturally align with the problem's
        # structure, Pascal's Triangle is a genuinely natural fit: the
        # triangle's ROWS *are* BFS levels. Draining the queue level by
        # level and building each full row before moving to the next is
        # exactly what "process one row, then the next" already means --
        # no forcing required here.

        # BFS State Encoding:
        #   - each queued item tracks a single piece of info:
        #   - value[(row, col)] holds the finalized value at that
        #     position, accumulated from contributions of its one or two
        #     parents in the row above before being read

        # Legal Next Moves:
        #   - From (row, col), propagate down-left to (row+1, col) and
        #     down-right to (row+1, col+1), as long as row+1 < numRows

        # Discovery vs. Accumulation:
        #   - A position is enqueued only the FIRST time it's discovered,
        #     so its own outgoing edges are only ever expanded once
        #   - But value[position] keeps ACCUMULATING every time a
        #     contribution into it arrives, even after it's enqueued --
        #     this correctly sums BOTH parent contributions before the
        #     position is itself dequeued and propagated forward

        # Safety Insight:
        # since edges only ever point to the NEXT row, every position in
        # row i is fully discovered and enqueued before row i+1 begins
        # processing (standard level-order guarantee), so by the time a
        # position is dequeued, both of its parent contributions have
        # already landed in its value

        # Edge Case:
        # a single row is just [1], no propagation needed
        if numRows == 1:
            return [[1]]

        # Result Rows:
        # sc: O(numRows^2), total cells across the whole triangle
        res = [[] for _ in range(numRows)]

        # Value Map:
        # value[(row, col)] accumulates contributions from parent cells
        # sc: O(numRows^2)
        value = {(0, 0): 1}

        # Iterative BFS Queue:
        #   - seed the queue with the single apex position
        queue = deque([(0, 0)])

        # Self Edges and Parallel Edges Safety Tracking:
        #   - mark starting position as visited (discovered)
        # sc: O(numRows^2)
        visited = {(0, 0)}

        # tc: O(numRows^2), every cell dequeued and expanded exactly once
        while queue:

            row, col = queue.popleft()

            # Record Finalized Value:
            #   - all contributions into (row, col) have already arrived
            #     (guaranteed by level-order processing), safe to record
            res[row].append(value[(row, col)])

            # No further propagation needed once the last row is reached
            if row == numRows - 1:
                continue

            # Explore Neighbors:
            #   - propagate this value down-left and down-right
            for nextCol in (col, col + 1):

                nextPos = (row + 1, nextCol)

                # Accumulate:
                #   - this cell's value contributes to both children
                #     directly below it
                # tc: O(1)
                value[nextPos] = value.get(nextPos, 0) + value[(row, col)]

                # Discovery Check:
                #   - only enqueue nextPos the first time it's
                #     discovered, so it propagates forward exactly once
                if nextPos not in visited:
                    visited.add(nextPos)
                    queue.append(nextPos)

        # overall: tc O(numRows^2) -- total cells across all rows sum to
        # 1+2+3+...+numRows = O(numRows^2)
        # overall: sc O(numRows^2) -- value map, visited set, queue, and
        # output all bounded by total cell count
        return res

    def generate(self, numRows: int) -> List[List[int]]:

        # Build Pascal's Triangle row by row, each row derived from the last

        # Note:
        # Every row starts and ends with 1. Every interior value is the
        # sum of the two values directly above it in the PREVIOUS row --
        # so each row only ever depends on the row immediately before it,
        # never anything further back.
        # 1. Start each new row with a leading 1
        # 2. For each interior position, sum the two adjacent values from
        #    the previous row (triangle[i-1][j-1] and triangle[i-1][j])
        # 3. Close each row (past the first) with a trailing 1
        # Result -> list of numRows rows forming Pascal's Triangle

        # Build Ex (numRows=5):
        # row 0:       [1]
        # row 1:       [1, 1]
        # row 2:       [1, 2, 1]        <- 2 = row1[0] + row1[1] = 1+1
        # row 3:       [1, 3, 3, 1]     <- 3 = row2[0] + row2[1] = 1+2
        # row 4:       [1, 4, 6, 4, 1]  <- 6 = row3[1] + row3[2] = 3+3

        dp = []

        # Build each row from the previous row

        # tc: O(numRows^2) -- row i has i+1 elements, summed over all rows
        for i in range(numRows):

            dpRow = [1]  # every row starts with a leading 1

            # Fill interior values from the row above
            for j in range(1, i):
                dpRow.append(dp[i - 1][j - 1] + dp[i - 1][j])

            # Close the row with a trailing 1 (skip for row 0)
            if i > 0:
                dpRow.append(1)

            dp.append(dpRow)

        # overall: tc O(numRows^2)
        # overall: sc O(numRows^2)
        return dp

  oh! pseudocode hasn't been written yet, try another card! :)

    def getRow(self, rowIndex: int) -> List[int]:

        # BFS Over The Implicit "Position" Graph
        #   - each cell (row, col) in the triangle is an implicit node,
        #     no literal graph is built up front
        #   - an edge connects (row, col) to (row+1, col) and to
        #     (row+1, col+1), since each value contributes to the TWO
        #     values directly below it in the next row

        # Note:
        # Same natural fit as #118 -- the triangle's rows ARE BFS levels,
        # so draining the queue level by level already matches "process
        # one row, then the next." The difference here is #119 only
        # needs the FINAL row returned, not every row stored -- so once
        # a cell has propagated its value to both children, its own
        # entry is deleted from the value map. This keeps the value map
        # (and therefore total extra space) bounded to O(rowIndex) at
        # any given moment, rather than O(rowIndex^2) for the whole
        # triangle, directly answering the follow-up's space constraint.

        # BFS State Encoding:
        #   - each queued item tracks a single piece of info:
        #   - value[(row, col)] holds the finalized value at that
        #     position, accumulated from contributions of its one or two
        #     parents in the row above before being read

        # Legal Next Moves:
        #   - From (row, col), propagate down-left to (row+1, col) and
        #     down-right to (row+1, col+1), as long as row+1 <= rowIndex

        # Discovery vs. Accumulation:
        #   - A position is enqueued only the FIRST time it's discovered,
        #     so its own outgoing edges are only ever expanded once
        #   - value[position] keeps ACCUMULATING every time a
        #     contribution into it arrives, even after it's enqueued --
        #     this correctly sums BOTH parent contributions before the
        #     position is itself dequeued and propagated forward

        # Space Pruning:
        #   - once a cell has been dequeued and propagated to both of
        #     its children, its entry is no longer needed by anything
        #     else in the graph (no cell reads a grandparent's value
        #     directly) -- so it's safe to delete, keeping the value map
        #     from growing past O(rowIndex) entries at once

        # Safety Insight:
        # since edges only ever point to the NEXT row, every position in
        # row i is fully discovered and enqueued before row i+1 begins
        # processing (standard level-order guarantee), so by the time a
        # position is dequeued, both of its parent contributions have
        # already landed in its value

        # Edge Case:
        # row 0 is just [1], no propagation needed
        if rowIndex == 0:
            return [1]

        # Value Map:
        # value[(row, col)] accumulates contributions from parent cells;
        # entries are deleted once fully propagated, bounding size to
        # O(rowIndex) at any moment
        # sc: O(rowIndex)
        value = {(0, 0): 1}

        # Iterative BFS Queue:
        #   - seed the queue with the single apex position
        # sc: O(rowIndex)
        queue = deque([(0, 0)])

        # Self Edges and Parallel Edges Safety Tracking:
        #   - mark starting position as visited (discovered)
        # sc: O(rowIndex)
        visited = {(0, 0)}

        # Target Row Buffer:
        # only the target row's values are collected for the final result
        # sc: O(rowIndex)
        result_row = [0] * (rowIndex + 1)

        # tc: O(rowIndex^2), every cell across all rows dequeued once
        while queue:

            row, col = queue.popleft()

            curr_value = value[(row, col)]

            # Target Row Reached:
            #   - record this cell's finalized value into the answer
            if row == rowIndex:
                result_row[col] = curr_value

            # Prune:
            #   - this cell's value has now been read; if it's not the
            #     target row it will never be needed again once
            #     propagated below, so remove it to bound space
            del value[(row, col)]

            # No further propagation needed once the target row is reached
            if row == rowIndex:
                continue

            # Explore Neighbors:
            #   - propagate this value down-left and down-right
            for nextCol in (col, col + 1):

                nextPos = (row + 1, nextCol)

                # Accumulate:
                #   - this cell's value contributes to both children
                #     directly below it
                # tc: O(1)
                value[nextPos] = value.get(nextPos, 0) + curr_value

                # Discovery Check:
                #   - only enqueue nextPos the first time it's
                #     discovered, so it propagates forward exactly once
                if nextPos not in visited:
                    visited.add(nextPos)
                    queue.append(nextPos)

        # overall: tc O(rowIndex^2) -- total cells across all rows sum to
        # 1+2+...+(rowIndex+1) = O(rowIndex^2)
        # overall: sc O(rowIndex) -- value map, visited set, and queue
        # never hold more than roughly one row's worth of entries at a
        # time due to pruning, matching the follow-up's O(rowIndex)
        # extra-space requirement (excluding the O(rowIndex) output
        # itself)
        return result_row

    def getRow(self, rowIndex: int) -> List[int]:

        # Build ONLY the target row of Pascal's Triangle, updating a
        # single list in place instead of storing every previous row

        # Note:
        # stores every row because it needs to RETURN all of them.
        # Here we only need the FINAL row, so we can reuse one list and
        # update it in place each iteration -- O(rowIndex) space instead
        # of O(rowIndex^2).
        #
        # The trick: update each row RIGHT TO LEFT, not left to right.
        # row[j] = row[j] + row[j-1] needs BOTH of those values from the
        # PREVIOUS row (not yet overwritten this iteration). If we walked
        # left to right, row[j-1] would already have been overwritten
        # with the CURRENT row's value by the time we read it -- corrupting
        # the calculation. Walking right to left guarantees row[j-1] is
        # still the old (previous row's) value when we use it.
        # 1. Start with row = [1] (row 0)
        # 2. For each subsequent row: extend the list by one (new trailing 1),
        #    then update interior values right to left using the OLD values
        #    still sitting to the left, which haven't been touched yet
        # Result -> the target row, built with O(rowIndex) space

        # Build Ex (rowIndex=3):
        # row 0: [1]
        # row 1: [1, 1]                    <- extend, then no interior to update
        # row 2: [1, 2, 1]                 <- j=1: row[1]+row[0] = 1+1 = 2
        # row 3: [1, 3, 3, 1]              <- j=2: row[2]+row[1] = 1+2 = 3 (old values)
        #                                      j=1: row[1]+row[0] = 2+1 = 3

        row = [1]

        # tc: O(rowIndex^2) -- row i has i+1 elements, summed over all rows
        for i in range(1, rowIndex + 1):
            row.append(1)  # extend row by one, trailing 1 placeholder

            for j in range(len(row) - 2, 0, -1):
                row[j] += row[j - 1]

        # overall: tc O(rowIndex^2)
        # overall: sc O(rowIndex)
        return row

    def minDays(self, n: int) -> int:

        # BFS Over The Implicit "Score So Far" Graph
        #   - each (score, streakVal) pair is an implicit node, no literal
        #     graph is built up front
        #   - an edge connects (score, streakVal) to (score + streakVal,
        #     streakVal + 1) by "earning" today, or to (score, 1) by
        #     "skipping" today and resetting the streak
        #   - every edge costs exactly 1 day, so BFS level order guarantees
        #     the first time score == n is reached, that level number is
        #     the minimum number of days

        # BFS State Encoding:
        #   - each queued item tracks 2 pieces of info:
        #   - score => total points earned so far
        #   - streakVal => points the NEXT earn-day would award

        # Legal Next Moves:
        #   - Earn: only legal if score + streakVal <= n, since
        #     overshooting past n can never be undone
        #   - Skip: always legal, resets streakVal back to 1

        # Self Edges and Parallel Edges Safety:
        #   - Once a (score, streakVal) state has been visited, BFS has
        #     already reached it via the fewest possible days, so we can
        #     safely skip requeuing it

        # Edge Case:
        # n = 0 needs zero days, score already matches target
        if n == 0:
            return 0

        # Iterative BFS Queue:
        #   - seed the queue with the starting state: score 0, next earn
        #     day would award 1 point
        # sc: O(n) worst case, queue can hold many in-flight states
        queue = deque([(0, 1)])

        # Self Edges and Parallel Edges Safety Tracking:
        #   - mark starting state as visited
        # sc: O(n * sqrt(n)) worst case, bounded by distinct (score,
        # streakVal) pairs reachable
        visited = {(0, 1)}

        # BFS Depth Level:
        #   - tracking min number of days used to reach current depth level
        days = 0

        while queue:

            days += 1

            # Level By Level Expansion:
            #   - drain entire current level before incrementing days
            #   - guarantees every state discovered in this pass used the
            #     same number of days from the start
            for _ in range(len(queue)):

                score, streakVal = queue.popleft()

                # Move 1 - Earn:
                #   - only legal if it doesn't overshoot n
                if score + streakVal <= n:

                    nextScore = score + streakVal

                    # Check:
                    #   - if we've hit exactly n, we are guaranteed to
                    #     have the minimum number of days
                    if nextScore == n:
                        return days

                    nextState = (nextScore, streakVal + 1)

                    # Early Pruning:
                    #   - enqueue new state if not already visited
                    if nextState not in visited:
                        visited.add(nextState)
                        queue.append(nextState)

                # Move 2 - Skip:
                #   - always legal, resets streak back to 1
                skipState = (score, 1)

                if skipState not in visited:
                    visited.add(skipState)
                    queue.append(skipState)

        # overall: tc O(n * sqrt(n)) worst case -- bounded by distinct
        # (score, streakVal) states, streakVal capped around O(sqrt(n))
        # since streaks grow triangularly
        # overall: sc O(n * sqrt(n)) -- visited set and queue hold up to
        # that many states
        return -1

    def minDays(self, n: int) -> int:

        # Note:
        # Minimum days to reach exactly n points using Top Down
        # Recursion with Memoization.

        # Streak Choice:
        # From any current score, choose to run a NEW streak (after an
        # optional single skip day to reset, unless this is the very
        # first action of the game) for some number of days, earning
        # points 1, 2, 3, ... for each day of that streak, then continue
        # from the resulting score. Every possible streak length that
        # doesn't overshoot n is tried -- including stopping mid-streak,
        # since skipping before a streak naturally ends may be required
        # to land exactly on n instead of overshooting it.

        # Subproblem Framing:
        # dfs(score) depends on dfs(score + 1), dfs(score + 1+2),
        # dfs(score + 1+2+3), ... for every streak length that keeps
        # score + added <= n. These are LARGER scores than the current
        # one -- recursion moves forward toward n, unlike a typical
        # "remaining count down to 0" recursion, but it's still
        # well-founded since score strictly increases on every call and
        # is capped at n.

        # Top Down Recursion With Memoization

        # Each distinct score is a subproblem, explored recursively by
        # trying every streak length as the "next" block of days played.
        # dfs(score) returns the fewest days needed to go from score to
        # exactly n, built from the answers to subproblems with larger
        # (closer to n) scores already solved deeper in the recursion.

        # Memoization:
        # since the same score can be reached through many different
        # sequences of streaks/skips, caching each result the first time
        # it's computed avoids recomputing that subproblem again

        # Safety Insight:
        # once score is in memo, we know every streak choice from it has
        # already been explored, so we can return the cached minimum
        # directly instead of re-branching

        # Sentinel:
        # represents "not possible (yet)", so any real day count will
        # always be smaller and win the min() comparison
        sentinel = float('inf')

        # Memo Cache:
        # memo[score] = min days needed to go from score to exactly n
        # sc: O(n)
        memo = {}

        def dfs(score):

            # Boundary Check:
            # exact target reached, no more days needed
            if score == n:
                return 0

            # Memo Check:
            # subproblem already solved, return cached result
            if score in memo:
                return memo[score]

            curr_min = sentinel

            streak = 1
            added = 0

            # Explore Choices:
            # try every streak length as the next block of days played
            while score + added + streak <= n:

                added += streak

                # Reset Day:
                # a skip day is needed to start a fresh streak UNLESS
                # this is the very first action of the game (score == 0)
                reset = 0 if score == 0 else 1

                # Check if using this streak length beats the current best
                use_streak = dfs(score + added) + streak + reset
                curr_min = min(curr_min, use_streak)

                streak += 1

            # All streak choices explored, cache and return the best found
            memo[score] = curr_min
            return memo[score]

        # Result:
        # kick off recursion from the starting score of 0
        res = dfs(0)

        # overall: tc O(n * sqrt(n)) -- O(n) distinct scores, each trying
        # up to O(sqrt(n)) streak lengths before the streak's running
        # total exceeds n
        # overall: sc O(n) -- memo cache plus recursion stack depth
        return res

    def minDays(self, n: int) -> int:

        # Note:
        # Minimum days to reach exactly n points using Bottom Up
        # Iterative Tabulation.

        # DP Table:
        # dp[score] = fewest days needed to go from score to exactly n
        # dp[n] = 0, ..., dp[0] = final answer


        # Bottom Up Iterative Tabulation

        # Each index score in dp represents a subproblem already solved
        # for every LARGER score closer to n by the time it's needed.
        # dp[score] is computed by trying every streak length as the next
        # block of days played, reusing the already-solved answer for the
        # resulting larger score at dp[score + added].

        # Build Order:
        # since dp[score] only ever depends on dp[score'] for score' >
        # score, solving strictly from n down to 0 guarantees every
        # dependency is already filled in by the time it's needed

        # Safety Insight:
        # once dp[score+1] through dp[n] are finalized, we know every
        # streak combination for those larger scores has already been
        # explored, so dp[score] can be built directly from those results

        # Sentinel:
        # represents "not possible (yet)", so any real day count will
        # always be smaller and win the min() comparison
        sentinel = float('inf')

        # DP Array:
        # dp[score] = min days needed to go from score to exactly n
        # dp[n] = 0, target already reached, no more days needed
        # sc: O(n)
        dp = [sentinel] * (n + 1)
        dp[n] = 0

        # Iterate n-1 Down To 0:
        # solve every subscore in decreasing order
        # tc: O(n * sqrt(n))
        for score in range(n - 1, -1, -1):

            streak = 1
            added = 0

            # Explore Choices:
            # try every streak length as the next block of days played
            while score + added + streak <= n:

                added += streak

                # Reset Day:
                # a skip day is needed to start a fresh streak UNLESS
                # this is the very first action of the game (score == 0)
                reset = 0 if score == 0 else 1

                # Check if using this streak length beats the current best
                use_streak = dp[score + added] + streak + reset
                dp[score] = min(dp[score], use_streak)

                streak += 1

        # Result:
        # dp[0] holds the fewest days needed starting from 0 points
        res = dp[0]

        # overall: tc O(n * sqrt(n)) -- O(n) scores, each trying up to
        # O(sqrt(n)) streak lengths before the streak's running total
        # exceeds n
        # overall: sc O(n)
        return res

    def numSquares(self, n: int) -> int:

        # BFS Over The Implicit "Remaining Sum" Graph
        #   - each integer from 0 to n is a node in an implicit graph, with no literal graph built up front
        #   - an edge connects value v to value v - s for every perfect square s <= v, 
        #     since subtracting one perfect square from the remaining total is a single "move" toward reaching 0

        # BFS level by level:
        #   - the first time 0 is reached that level number is guaranteed to be the minimum number
        #     of perfect squares used.

        # BFS State Encoding:
        #   - each queued item tracks a single piece of info:
        #   - remaining => the value still left to reduce to 0

        # Legal Next Move:
        #   - From a state (remaining count), only subtracting a perfect square <= remaining is legal,
        #     since overshooting past 0 is never a valid move.

        # Self Edges and Parallel Edges Safety:
        #   - Once a remaining value has been visited, 
        #     we know BFS has already reached it via the fewest possible squares,
        #     so we can safely skip requeuing it.

        # Edge Case:
        # n is already a perfect square sum of itself, e.g. n = 0
        if n == 0:
            return 0

        # Precompute Perfect Squares:
        #   - generate every perfect square up to n once, 
        #      to be used as the "move set" at every level instead of recomputing per node
        # tc: O(sqrt(n))
        squares = []
        i = 1
        while i * i <= n:
            squares.append(i * i)
            i += 1

        # Iterative BFS Queue:
        #   - seed the queue with n itself, 0 squares used so far
        queue = deque([n])

        # Self Edges and Parallel Edges Safety Tracking:
        #    - mark starting remaining value as visited
        # sc: O(n)
        visited = {n}

        # BFS Depth Level
        #   - tracking min num of perfect squares used to reach current depth level
        count = 0

        while queue:

            count += 1

            # Level By Level Expansion:
            #   - drain entire current level before incrementing count
            #   - guarantees for every remaining value discovered in this pass to have
            #     the same number of squares (depth) used from n
            for _ in range(len(queue)):

                # Remaining value previous jump:
                remaining = queue.popleft()

                # Explore Neighbors:
                #   - subtract every perfect square that doesn't overshoot
                #     the current remaining value
                #   - squares is sorted ascending, so once sq > remaining
                #     every later square would too
                for sq in squares:

                    if sq > remaining:
                        break

                    nextRemaining = remaining - sq

                    # Check:
                    #   - if we've hit exactly 0, we are guaranteed to have
                    #     the minimum number of perfect squares
                    if nextRemaining == 0:
                        return count

                    # Early Pruning:
                    #   - enque new state (nextRemaining) if not already visited
                    if nextRemaining not in visited:
                        visited.add(nextRemaining)
                        queue.append(nextRemaining)

        # All reachable remaining values processed without hitting 0,
        # which can't actually happen since 0 is always reachable by
        # repeatedly subtracting 1x1 squares

        # overall: tc O(n * sqrt(n))
        # overall: sc O(n)
        return -1

    def numSquares(self, n: int) -> int:

        # Note:
        # Minimum perfect squares that sum to a target
        # using Top Down Recursion with Memoization

        # Squares:
        # n = 12, perfect squares <= 12: [1, 4, 9]

        # Subproblem Framing:
        # dfs(12) depends on dfs(11), dfs(8), dfs(3)
        # dfs(11) depends on dfs(10), dfs(7), dfs(2)
        # ... overlapping subproblems, memoized to avoid recompute


        # Top Down Recursion With Memoization

        # Each distinct remaining value is a subproblem, explored
        # recursively by trying every perfect square as the "last"
        # square used. dfs(curr_remaining) returns the fewest perfect
        # squares needed to make curr_remaining, built from the answers
        # to smaller subproblems already solved deeper in the recursion.

        # Memoization:
        # since the same remaining value can be reached through many
        # different combinations of squares, caching each result the
        # first time it's computed avoids recomputing that subproblem again

        # Safety Insight:
        # once curr_remaining is in memo, we know every square
        # combination reaching it has already been explored, so we can
        # return the cached minimum directly instead of re-branching

        # Sentinel:
        # represents "not possible (yet)", so any real square count will
        # always be smaller and win the min() comparison
        sentinel = float('inf')

        # Precompute Perfect Squares:
        # generate every perfect square up to n once, reused as the
        # "move set" at every recursive call instead of recomputing
        # tc: O(sqrt(n))
        squares = []
        i = 1
        while i * i <= n:
            squares.append(i * i)
            i += 1

        # Memo Cache:
        # memo[curr_remaining] = min squares needed to make curr_remaining
        # sc: O(n)
        memo = {}

        def dfs(curr_remaining):

            # Memo Check:
            # subproblem already solved, return cached result
            if curr_remaining in memo:
                return memo[curr_remaining]

            # Boundary Check:
            # exact remaining reached, no more squares needed
            if curr_remaining == 0:
                return 0

            curr_min = sentinel

            # Explore Choices:
            # try using each perfect square as the next square taken
            for sq in squares:

                # Early Prune:
                # stop once the square overshoots past 0, since squares
                # is sorted ascending and every later square would too
                if sq > curr_remaining:
                    break

                # Check if using this square beats the current best
                use_square = dfs(curr_remaining - sq)
                curr_min = min(curr_min, use_square + 1)

            # All square choices explored, cache and return the best found
            memo[curr_remaining] = curr_min
            return memo[curr_remaining]

        # Result:
        # kick off recursion from the full value n
        res = dfs(n)

        # overall: tc O(n * sqrt(n))
        # overall: sc O(n)
        return res

    def numSquares(self, n: int) -> int:

        # Note:
        # Minimum perfect squares that sum to a target
        # using Bottom Up Iterative Tabulation

        # Squares:
        # n = 12, perfect squares <= 12: [1, 4, 9]

        # DP Table:
        # dp[v] = fewest squares needed to make value v
        # dp[0] = 0, dp[1] = 1, dp[4] = 1, ..., dp[12] = 3


        # Bottom Up Iterative Tabulation

        # Each index v in dp represents the smallest subvalue solved
        # so far, built up from 0 to n. dp[v] is computed by trying
        # every perfect square as the "last" square used, reusing the
        # already-solved answer for the smaller remaining value at
        # dp[v - sq].

        # Build Order:
        # since dp[v] only ever depends on dp[v - sq] for sq < v,
        # solving strictly left to right guarantees every dependency
        # is already filled in by the time it's needed

        # Safety Insight:
        # once dp[0] through dp[v - 1] are finalized, we know every
        # square combination for smaller values has already been
        # explored, so dp[v] can be built directly from those results

        # Sentinel:
        # represents "not possible (yet)", so any real square count will
        # always be smaller and win the min() comparison
        sentinel = float('inf')

        # Precompute Perfect Squares:
        # generate every perfect square up to n once, reused as the
        # "move set" at every iteration instead of recomputing
        # tc: O(sqrt(n))
        squares = []
        i = 1
        while i * i <= n:
            squares.append(i * i)
            i += 1

        # DP Array:
        # dp[v] = min squares needed to make value v
        # dp[0] = 0, no squares needed to make value 0
        # sc: O(n)
        dp = [0] * (n + 1)

        # Iterate 1 To n:
        # solve every subvalue in increasing order
        # tc: O(n * sqrt(n))
        for v in range(1, n + 1):

            curr_min = sentinel

            # Explore Choices:
            # try using each perfect square as the next square taken
            for sq in squares:

                # Early Prune:
                # stop once the square overshoots past v, since squares
                # is sorted ascending and every later square would too
                if sq > v:
                    break

                # Check if using this square beats the current best
                use_square = dp[v - sq] + 1
                curr_min = min(curr_min, use_square)

            dp[v] = curr_min

        # Result:
        # n is always reachable (worst case, all 1x1 squares), so no
        # sentinel check needed here unlike Coin Change
        res = dp[n]

        # overall: tc O(n * sqrt(n))
        # overall: sc O(n)
        return res

  oh! pseudocode hasn't been written yet, try another card! :)

    def coinChange(self, coins: List[int], amount: int) -> int:

        # BFS Over The Implicit "Remaining Amount" Graph
        # - each integer from 0 to amount is a node in an implicit graph,
        #   with no literal graph built up front.
        # - an edge connects value r to value r - c for every coin
        #   denomination c <= r, since subtracting one coin from the
        #   remaining amount is a single "move" toward reaching 0.

        # BFS explores remaining amounts level by level:
        #   - the first time 0 is reached
        #   - that level number is guaranteed to be the minimum number
        #     of coins used.

        # BFS State Encoding:
        #   - each queued item tracks two pieces of info:
        #       - rem   => the amount still left to reduce to 0
        #       - steps => the number of coins used to reach rem so far

        # Legal Next Move:
        #   - From a state (rem, steps),
        #   - only subtracting a coin <= rem is legal,
        #   - since overshooting past 0 is never a valid move.

        # Self Edges and Parallel Edges Safety:
        #   - Once a remaining value has been visited, we know BFS has
        #     already reached it via the fewest possible coins,
        #     so we can safely skip requeuing it.

        # Edge Case:
        # amount is already 0, no coins needed
        if amount == 0:
            return 0

        # Iterative BFS Queue:
        #   - seed the queue with amount itself, 0 coins used so far
        queue = deque([(amount, 0)])

        # Self Edges and Parallel Edges Safety Tracking:
        #    - mark starting remaining value as visited
        # sc: O(amount)
        visitedValues = {amount}

        while queue:

            # Remaining value previous jump:
            rem, steps = queue.popleft()

            # Explore Neighbors:
            #   - try to subtract every coin that doesn't overshoot rem
            for coin in coins:

                # Curr coin step
                nextRem = rem - coin

                # Check:
                #   - if we've hit exactly 0, we are guaranteed to have
                #     the minimum number of coins
                if nextRem == 0:
                    return steps + 1

                # Early Pruning:
                #   - enque new state (next_rem) if valid and not already visited
                elif 0 < nextRem and nextRem not in visitedValues:
                    visitedValues.add(nextRem)
                    queue.append((nextRem, steps+1))

        # All reachable remaining values processed without hitting 0,
        # no combination of coins can make up the amount

        # overall: tc O(amount * len(coins))
        # overall: sc O(amount)
        return -1

    def coinChange(self, coins: List[int], amount: int) -> int:
        
        # Note:
        # Minimum coins to reach a target amount using Bottom Up Iterative Tabulation

        # Coins:
        # coins = [1, 2, 5], amount = 11

        # DP Table:
        # dp[n] = fewest coins needed to make amount n
        # dp[0] = 0, dp[1] = 1, dp[2] = 1, ..., dp[11] = 3

        # Sentinel:
        # represents "not possible (yet)", 
        # so any real coin count will always be smaller and win the min() comparison
        sentinel = float('inf')

        # DP Array:
        # dp[a] = min coins needed to make amount 'a'
        # dp[0] = 0, since no coins needed to make amount 0
        # sc: O(amount)
        dp = [0] * (amount + 1)

        # Iterate 1 to Amount:
        # solve every subamount in increasing order
        # tc: O(amount * len(coins))
        for currTarget in range(1, amount + 1):

            # local min
            currMin = sentinel

            # Explore Choices:
            # try using each coin denomination as the next coin taken
            for coin in coins:

                # Early Prune:
                # skip coins that would overshoot past 0
                prevTarget = currTarget - coin

                if 0 <= prevTarget:

                    # Since we are moving from 0..amount,
                    # dp[prevTarget] already stores its min coin count,
                    # So we would like to jump from that prevTarget to currTarget,
                    # so we need to add 1 coin for this jump
                    prevMin = dp[prevTarget] + 1
                    currMin = min(currMin, prevMin)

            dp[currTarget] = currMin

        # Min Coins:
        # coins for amount was either set to sentinel during iteration,
        # or we found a min num of coins
        if dp[amount] != sentinel:
            res = dp[amount]
        else:
            res = -1

        # overall: tc O(amount * len(coins))
        # overall: sc O(amount)
        return res

  oh! pseudocode hasn't been written yet, try another card! :)

    def change(self, amount: int, coins: list[int]) -> int:

        # DP Array:
        # dp[target] = number of combinations that make target
        # dp[0] = 1, since there is exactly 1 way to make 0 via choosing no coins
        # sc: O(amount)
        dp = [0] * (amount + 1)
        dp[0] = 1

        # Iterate Coins:
        # process each coin one at a time so 
        # that each combination is counted only once, 
        # regardless of the order of its coins
        # tc: O(amount * len(coins))
        for coin in coins:

            # Iterate Targets:
            # start at coin because smaller targets cannot use this coin
            # iterate forward so the current coin can be reused
            for currTarget in range(coin, amount + 1):

                # Jump to PrevTarget:
                # coin allows us to connect CurrTarget to PrevTarget
                prevTarget = currTarget - coin

                # Multiple New Way To Reach CurrTarget:
                # the number of ways we can reach prevTarget
                # now connects to currTarget via the coin we just grabbed
                dp[currTarget] += dp[prevTarget]

        # Result:
        # dp[amount] contains the total number of unique combinations

        # overall: tc O(amount * len(coins))
        # overall: sc O(amount)
        return dp[amount]

  oh! pseudocode hasn't been written yet, try another card! :)

    def rob(self, nums: List[int]) -> int:
        
        # BFS Over The Implicit "House" Graph
        #   - each house index i is an implicit node, no literal graph
        #     is built up front
        #   - an edge connects house i to house i+1 (the SKIP option --
        #     if house i+1 isn't robbed, its best loot is at least
        #     whatever house i already achieved) and to house i+2 (the
        #     ROB option -- robbing house i+2 adds nums[i+2] on top of
        #     whatever house i achieved, since i+1 must be skipped)

        # Note:
        # Unlike Tribonacci's BFS (sum aggregation), this is a MAX
        # aggregation -- each node's final value is the BEST of the
        # candidates pushed into it, not the sum of them. Two edges can
        # push a candidate into the same node (skip-candidate from i-1,
        # rob-candidate from i-2), and the node takes whichever is
        # larger. Since edges only ever point to LARGER indices, FIFO
        # discovery order still coincides with topological order, so by
        # the time a node is dequeued both of its candidates have
        # already arrived.

        # BFS State Encoding:
        #   - each queued item is simply a house index i
        #   - value[i] accumulates the MAX of all candidates pushed into
        #     it from predecessors i-1 (skip) and i-2 (rob), finalized
        #     before i itself is dequeued and propagated forward

        # Legal Next Moves:
        #   - From house i, push a skip-candidate to i+1 and a
        #     rob-candidate to i+2, as long as neither overshoots n-1

        # Discovery vs. Accumulation:
        #   - A house is enqueued only the FIRST time it's discovered,
        #     so it propagates its own (now-finalized) value forward
        #     exactly once
        #   - value[house] keeps taking the MAX of every candidate that
        #     arrives, even after it's enqueued -- this correctly
        #     resolves "rob or skip" at each house before it's read

        # Safety Insight:
        # because edges only ever point to LARGER indices, a house's
        # predecessors (i-1, i-2) are always discovered and enqueued no
        # later than the house itself, so by the time house i is
        # dequeued, value[i] already holds its FINAL max and is safe to
        # propagate forward

        n = len(nums)

        # Base Cases:
        # house 0 has no predecessors -- its value is just its own loot
        # house 1 has one real choice -- rob house 0 or house 1, whichever
        # is bigger (no house -1 to rob-chain from)
        if n == 1:
            return nums[0]

        # Value Array:
        # value[i] = max loot achievable using houses[0..i]
        # sc: O(n)
        value = [0] * n
        value[0] = nums[0]
        value[1] = max(nums[0], nums[1])

        # Iterative BFS Queue:
        #   - seed the queue with both base houses, since each
        #     independently starts propagating candidates forward
        queue = deque([0, 1])

        # Self Edges and Parallel Edges Safety Tracking:
        #   - mark both base houses as visited (discovered), so each
        #     only ever propagates forward once
        # sc: O(n)
        visited = {0, 1}

        # tc: O(n), each house dequeued and expanded exactly once
        while queue:

            i = queue.popleft()

            # Explore Neighbors:
            #   - push a skip-candidate to i+1
            #   - push a rob-candidate to i+2
            for move in (1, 2):

                j = i + move

                # Legal Move Check:
                #   - skip any propagation that overshoots the last house
                if j > n - 1:
                    continue

                # Candidate Calculation:
                #   - move == 1: SKIP house j -> inherit value[i] as-is
                #   - move == 2: ROB house j -> value[i] + nums[j]
                candidate = value[i] if move == 1 else value[i] + nums[j]

                # Accumulate:
                #   - take the better of this candidate vs whatever
                #     value[j] already holds
                # tc: O(1)
                value[j] = max(value[j], candidate)

                # Discovery Check:
                #   - only enqueue j the first time it's discovered, so
                #     it propagates its own finalized value forward
                #     exactly once
                if j not in visited:
                    visited.add(j)
                    queue.append(j)

        # Result:
        # value[n-1] holds the max loot considering all n houses, having
        # resolved every rob/skip candidate that ever arrived at it
        res = value[n - 1]

        # overall: tc O(n)
        # overall: sc O(n)
        return res