Dynamic Programming (Hard)Master the art of optimization using subproblems, memoization, and tabulation.

302. Climbing Stairs

Problem Statement

You are climbing a staircase. It takes `n` steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? **Example:** ```python Input: n = 3 Output: 3 Explanation: 1+1+1, 1+2, 2+1 ```

Approach

1. **Subproblem**: Reaching step `i` depends on step `i-1` (1 jump) and `i-2` (2 jumps). 2. **Recurrence**: `dp[i] = dp[i-1] + dp[i-2]`. 3. **Base Cases**: `dp[1] = 1`, `dp[2] = 2`. 4. **Optimization**: Logic is identical to Fibonacci. Space can be O(1) by storing only last two values.

Solution

def climbStairs(n):
    if n <= 2:
        return n
        
    one_step_before = 2
    two_steps_before = 1
    
    for _ in range(3, n + 1):
        current = one_step_before + two_steps_before
        two_steps_before = one_step_before
        one_step_before = current
        
    return one_step_before

303. House Robber

Problem Statement

You are a professional robber planning to rob houses along a street. Adjacent houses have security systems connected and **it will automatically contact the police if two adjacent houses were broken into on the same night**. Given an integer array `nums` representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police. **Example:** ```python Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total = 4. ```

Approach

1. **Decision**: At house `i`, rob it or skip it. 2. **Recurrence**: * Rob `i`: Get `nums[i]` + max money from `i-2`. * Skip `i`: Get max money from `i-1`. * `dp[i] = max(nums[i] + dp[i-2], dp[i-1])`.

Solution

def rob(nums):
    rob1, rob2 = 0, 0
    
    for n in nums:
        # [rob1, rob2, n, n+1, ...]
        new_rob = max(rob1 + n, rob2)
        rob1 = rob2
        rob2 = new_rob
        
    return rob2

304. Coin Change

Problem Statement

You are given an integer array `coins` representing coins of different denominations and an integer `amount` representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return `-1`. **Example:** ```python Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1 ```

Approach

1. **Unbounded Knapsack**: We can use coins multiple times. 2. **Bottom-Up Approach**: * `dp[a]` = min coins to make amount `a`. * Initialize `dp[0] = 0`, others to infinity. * Loop `a` from 1 to `amount`. * Loop each `c` in `coins`. * If `a - c >= 0`: `dp[a] = min(dp[a], 1 + dp[a-c])`.

Solution

def coinChange(coins, amount):
    # Initialize with amount + 1 (impossible max value)
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0
    
    for a in range(1, amount + 1):
        for c in coins:
            if a - c >= 0:
                dp[a] = min(dp[a], 1 + dp[a - c])
                
    return dp[amount] if dp[amount] != amount + 1 else -1

305. Longest Increasing Subsequence

Problem Statement

Given an integer array `nums`, return the length of the longest strictly increasing subsequence. **Example:** ```python Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. ```

Approach

1. **State**: `dp[i]` = length of LIS ending at index `i`. 2. **Transitions**: * Compare `nums[i]` with all previous `nums[j]` (where `j < i`). * If `nums[i] > nums[j]`, we can extend the LIS ending at `j`. * `dp[i] = max(dp[i], 1 + dp[j])`. 3. **Result**: Max value in `dp`.

Solution

def lengthOfLIS(nums):
    dp = [1] * len(nums)
    
    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], 1 + dp[j])
                
    return max(dp) if nums else 0

306. Longest Common Subsequence

Problem Statement

Given two strings `text1` and `text2`, return the length of their longest common subsequence. If there is no common subsequence, return 0. A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. **Example:** ```python Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace". ```

Approach

1. **2D DP Grid**: `dp[i][j]` represents LCS of `text1[:i]` and `text2[:j]`. 2. **Logic**: * If characters match (`text1[i] == text2[j]`): `dp[i][j] = 1 + dp[i-1][j-1]`. * If no match: `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`. 3. **Setup**: Use size `(m+1) x (n+1)` with zeros to handle base cases easily.

Solution

def longestCommonSubsequence(text1, text2):
    dp = [[0 for j in range(len(text2) + 1)] for i in range(len(text1) + 1)]
    
    for i in range(len(text1) - 1, -1, -1):
        for j in range(len(text2) - 1, -1, -1):
            if text1[i] == text2[j]:
                dp[i][j] = 1 + dp[i + 1][j + 1]
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])
                
    return dp[0][0]

Back

Dynamic Programming (Hard) / 302. Climbing Stairs

00:00

1/5

302. Climbing Stairs

Easy

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example:

Input: n = 3
Output: 3
Explanation: 1+1+1, 1+2, 2+1

1
Subproblem: Reaching step i depends on step i-1 (1 jump) and i-2 (2 jumps).
2
Recurrence: dp[i] = dp[i-1] + dp[i-2].
3
Base Cases: dp[1] = 1, dp[2] = 2.
4
Optimization: Logic is identical to Fibonacci. Space can be O(1) by storing only last two values.

PYTHON PLAYGROUND

⏳ Loading editor…