DP 1D Linear Pattern¶

# O(n) space
dp = [0] * (n + 1)
for i in range(2, n + 1):
    dp[i] = dp[i-1] + dp[i-2]
return dp[n]

# O(1) space
prev2, prev1 = 1, 1
for i in range(2, n + 1):
    prev2, prev1 = prev1, prev2 + prev1
return prev1

class Solution:
    """
    1D DP: Count ways to reach each step.

    State: dp[i] = number of distinct ways to reach step i
    Transition: dp[i] = dp[i-1] + dp[i-2]
        - Can reach step i from step (i-1) with 1 step
        - Can reach step i from step (i-2) with 2 steps
    Base: dp[0] = 1 (one way to stay at ground)
          dp[1] = 1 (one way to reach step 1)

    This is exactly the Fibonacci sequence!

    Time: O(n) | Space: O(1) with optimization
    """
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        # Space-optimized: only need last two values
        prev2 = 1  # dp[i-2]
        prev1 = 2  # dp[i-1]

        for step in range(3, n + 1):
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current

        return prev1

class Solution:
    """
    1D DP: Minimize cost to reach each step.

    State: dp[i] = minimum cost to reach step i
    Transition: dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
        - Pay cost[i] to step on this stair
        - Choose cheaper path from (i-1) or (i-2)
    Base: dp[0] = cost[0], dp[1] = cost[1]
        - Must pay cost to start from step 0 or 1

    Note: "Top" is beyond the last stair (index n).

    Time: O(n) | Space: O(1)
    """
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)

        # Space-optimized
        prev2 = cost[0]  # Cost to reach step 0
        prev1 = cost[1]  # Cost to reach step 1

        for i in range(2, n):
            current = min(prev1, prev2) + cost[i]
            prev2 = prev1
            prev1 = current

        # Can reach top from either last or second-to-last step
        return min(prev1, prev2)

class Solution:
    """
    1D DP: Include/Exclude decision at each step.

    State: dp[i] = maximum loot from houses[0..i]
    Transition: dp[i] = max(
        dp[i-1],           # Skip current house, keep previous best
        dp[i-2] + nums[i]  # Rob current house, add to best before adjacent
    )
    Base: dp[0] = nums[0], dp[1] = max(nums[0], nums[1])

    The classic "take or skip" pattern.

    Time: O(n) | Space: O(1)
    """
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]

        # Space-optimized
        prev2 = nums[0]                    # Best up to house i-2
        prev1 = max(nums[0], nums[1])      # Best up to house i-1

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

        return prev1

class Solution:
    """
    Circular DP: Split into two linear subproblems.

    Key Insight: First and last houses are adjacent, so we can't rob both.
    Solution: Take the maximum of two scenarios:
        1. Rob houses[0..n-2] (exclude last house)
        2. Rob houses[1..n-1] (exclude first house)

    This transforms circular DP into two linear DP problems.

    Time: O(n) | Space: O(1)
    """
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        # Helper: linear house robber on subarray
        def rob_linear(houses: List[int]) -> int:
            if not houses:
                return 0
            if len(houses) == 1:
                return houses[0]

            prev2 = houses[0]
            prev1 = max(houses[0], houses[1])

            for i in range(2, len(houses)):
                current = max(prev1, prev2 + houses[i])
                prev2 = prev1
                prev1 = current

            return prev1

        # Two scenarios: exclude last OR exclude first
        return max(
            rob_linear(nums[:-1]),  # Houses 0 to n-2
            rob_linear(nums[1:])   # Houses 1 to n-1
        )

class Solution:
    """
    Implicit 1D DP: Track best buy price for each potential sell day.

    Key Insight: For each day as potential sell day, the best buy day
    is the minimum price seen before it.

    State (implicit): min_price = lowest price up to current day
    Transition: max_profit = max(max_profit, price - min_price)

    Time: O(n) | Space: O(1)
    """
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')
        max_profit = 0

        for price in prices:
            # Update best buy price seen so far
            min_price = min(min_price, price)

            # Calculate profit if we sell today
            profit_if_sell_today = price - min_price

            # Update best profit
            max_profit = max(max_profit, profit_if_sell_today)

        return max_profit

def count_ways(n: int) -> int:
    """Count ways to reach step n (1 or 2 steps at a time)."""
    if n <= 2:
        return n

    prev2, prev1 = 1, 2
    for i in range(3, n + 1):
        prev2, prev1 = prev1, prev2 + prev1

    return prev1

def min_cost(costs: List[int]) -> int:
    """Minimum cost to reach beyond last step."""
    n = len(costs)
    if n == 1:
        return costs[0]

    prev2 = costs[0]
    prev1 = costs[1]

    for i in range(2, n):
        current = min(prev1, prev2) + costs[i]
        prev2, prev1 = prev1, current

    return min(prev1, prev2)

def max_non_adjacent(nums: List[int]) -> int:
    """Maximum sum of non-adjacent elements."""
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    prev2 = nums[0]
    prev1 = max(nums[0], nums[1])

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

    return prev1

def max_circular(nums: List[int]) -> int:
    """Maximum non-adjacent sum in circular array."""
    if len(nums) == 1:
        return nums[0]

    def max_linear(arr: List[int]) -> int:
        if len(arr) == 1:
            return arr[0]
        prev2 = arr[0]
        prev1 = max(arr[0], arr[1])
        for i in range(2, len(arr)):
            prev2, prev1 = prev1, max(prev1, prev2 + arr[i])
        return prev1

    return max(
        max_linear(nums[:-1]),  # Exclude last
        max_linear(nums[1:])    # Exclude first
    )

def max_profit_single_transaction(prices: List[int]) -> int:
    """Maximum profit from single buy-sell."""
    min_price = float('inf')
    max_profit = 0

    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)

    return max_profit

def solve_1d_dp(arr: List[int], combine, initial_values: List) -> int:
    """
    Generic 1D DP template.

    Args:
        arr: Input array
        combine: Function (prev2, prev1, current_val) -> new_value
        initial_values: Base case values [dp[0], dp[1], ...]
    """
    n = len(arr)
    if n <= len(initial_values):
        return initial_values[n - 1] if n > 0 else 0

    # Initialize from base cases
    prev_values = initial_values[:]

    for i in range(len(initial_values), n):
        new_value = combine(prev_values, arr[i])
        prev_values.pop(0)
        prev_values.append(new_value)

    return prev_values[-1]