Problems

Master dynamic programming by solving these carefully selected problems. Each problem demonstrates different DP techniques and builds your problem-solving skills progressively.

Pro Tip: Start with the Concept Guide to understand the theory, then use our code templates as reference while solving these problems.

Problem Categories

Easy Problems

1. Climbing Stairs

LeetCode 70 | Difficulty: Easy | Acceptance: 52.1%

Brief: Find how many distinct ways you can climb to the top of a staircase where you can take 1 or 2 steps at a time.

Why this pattern?: The number of ways to reach step n depends on the sum of ways to reach steps n-1 and n-2, creating overlapping subproblems.

Key Insight: This is essentially the Fibonacci sequence - each step’s solution builds on the previous two steps.

Visual State Transition:

  graph LR
    A[Step 0] --> B[Step 1]
    A --> C[Step 2]
    B --> D[Step 3]
    C --> D
    D --> E[Step 4]
    C --> E

Code Solution:

function climbStairs(n) {
    if (n <= 1) return 1;

    let prev2 = 1, prev1 = 1;

    for (let i = 2; i <= n; i++) {
        const current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

def climb_stairs(n):
    if n <= 1:
        return 1

    prev2, prev1 = 1, 1

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

    return prev1

public class Solution {
    public int climbStairs(int n) {
        if (n <= 1) return 1;

        int prev2 = 1, prev1 = 1;

        for (int i = 2; i <= n; i++) {
            int current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return 1;

        int prev2 = 1, prev1 = 1;

        for (int i = 2; i <= n; i++) {
            int current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
};

func climbStairs(n int) int {
    if n <= 1 {
        return 1
    }

    prev2, prev1 := 1, 1

    for i := 2; i <= n; i++ {
        current := prev1 + prev2
        prev2, prev1 = prev1, current
    }

    return prev1
}

def climb_stairs(n)
    return 1 if n <= 1

    prev2, prev1 = 1, 1

    (2..n).each do |i|
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    end

    prev1
end

2. House Robber

LeetCode 198 | Difficulty: Medium | Acceptance: 47.6%

Brief: Maximize money robbed from houses arranged in a line without robbing adjacent houses.

Why this pattern?: At each house, you must decide whether to rob it (adding its value to the solution from two houses back) or skip it (keeping the best solution from the previous house).

Key Insight: The optimal solution at house i is the maximum of robbing house i plus the best solution from house i-2, or the best solution from house i-1.

Visual State Transition:

  graph TD
    A[House 1] --> B[House 2]
    A --> C[House 3]
    B --> D[House 4]
    C --> D
    C --> E[House 5]
    D --> E

Code Solution:

function rob(nums) {
    if (!nums.length) return 0;

    let prev2 = 0, prev1 = nums[0];

    for (let i = 1; i < nums.length; i++) {
        const current = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

def rob(nums):
    if not nums:
        return 0

    prev2, prev1 = 0, nums[0]

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

    return prev1

public class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;

        int prev2 = 0, prev1 = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int current = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;

        int prev2 = 0, prev1 = nums[0];

        for (int i = 1; i < nums.size(); i++) {
            int current = max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
};

func rob(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    prev2, prev1 := 0, nums[0]

    for i := 1; i < len(nums); i++ {
        current := max(prev1, prev2+nums[i])
        prev2, prev1 = prev1, current
    }

    return prev1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

def rob(nums)
    return 0 if nums.empty?

    prev2, prev1 = 0, nums[0]

    (1...nums.length).each do |i|
        current = [prev1, prev2 + nums[i]].max
        prev2, prev1 = prev1, current
    end

    prev1
end

Medium Problems

3. Longest Increasing Subsequence

LeetCode 300 | Difficulty: Medium | Acceptance: 45.8%

Brief: Find the length of the longest strictly increasing subsequence in an integer array.

Why this pattern?: For each element, the longest increasing subsequence ending at that element depends on all previous elements that are smaller.

Key Insight: For each position i, check all previous positions j where nums[j] < nums[i] and extend the LIS ending at j.

Visual State Transition:

  graph TD
    A[Position 0] --> B[Position 1]
    A --> C[Position 2]
    B --> D[Position 3]
    C --> D
    C --> E[Position 4]
    D --> E

Code Solution:

function lengthOfLIS(nums) {
    if (!nums.length) return 0;

    const dp = new Array(nums.length).fill(1);

    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    return Math.max(...dp);
}

def length_of_lis(nums):
    if not nums:
        return 0

    dp = [1] * len(nums)

    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;

        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int max = 1;
        for (int val : dp) {
            max = Math.max(max, val);
        }
        return max;
    }
}

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;

        vector<int> dp(nums.size(), 1);

        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }

        return *max_element(dp.begin(), dp.end());
    }
};

func lengthOfLIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    dp := make([]int, len(nums))
    for i := range dp {
        dp[i] = 1
    }

    for i := 1; i < len(nums); i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
    }

    max := 1
    for _, val := range dp {
        if val > max {
            max = val
        }
    }
    return max
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

def length_of_lis(nums)
    return 0 if nums.empty?

    dp = Array.new(nums.length, 1)

    (1...nums.length).each do |i|
        (0...i).each do |j|
            if nums[i] > nums[j]
                dp[i] = [dp[i], dp[j] + 1].max
            end
        end
    end

    dp.max
end

4. Coin Change

LeetCode 322 | Difficulty: Medium | Acceptance: 39.5%

Brief: Find the fewest number of coins needed to make up a given amount using unlimited supply of given coin denominations.

Why this pattern?: The minimum coins needed for amount i can be found by considering all coin denominations and taking the minimum of (1 + coins needed for amount i - coin_value).

Key Insight: This is an unbounded knapsack problem where each coin can be used multiple times.

Visual State Transition:

Amount:  0  1  2  3  4  5
Coins:  [1, 2, 5]
DP:     [0, 1, 1, 2, 2, 3]

Process:
1. For coin=1: dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=4, dp[5]=5
2. For coin=2: dp[2]=min(2,1)=1, dp[3]=min(3,2)=2, dp[4]=min(4,3)=3, dp[5]=min(5,4)=4
3. For coin=5: dp[5]=min(4,1)=1

Code Solution:

function coinChange(coins, amount) {
    const dp = new Array(amount + 1).fill(amount + 1);
    dp[0] = 0;

    for (const coin of coins) {
        for (let i = coin; i <= amount; i++) {
            dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
    }

    return dp[amount] === amount + 1 ? -1 : dp[amount];
}

def coin_change(coins, amount):
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

    return -1 if dp[amount] == amount + 1 else dp[amount]

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }

        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
}

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }

        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
};

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := range dp {
        dp[i] = amount + 1
    }
    dp[0] = 0

    for _, coin := range coins {
        for i := coin; i <= amount; i++ {
            dp[i] = min(dp[i], dp[i-coin]+1)
        }
    }

    if dp[amount] == amount+1 {
        return -1
    }
    return dp[amount]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

def coin_change(coins, amount)
    dp = Array.new(amount + 1, amount + 1)
    dp[0] = 0

    coins.each do |coin|
        (coin..amount).each do |i|
            dp[i] = [dp[i], dp[i - coin] + 1].min
        end
    end

    dp[amount] == amount + 1 ? -1 : dp[amount]
end

5. Edit Distance

LeetCode 72 | Difficulty: Hard | Acceptance: 51.3%

Brief: Find the minimum number of operations (insert, delete, replace) required to convert word1 to word2.

Why this pattern?: The edit distance between prefixes of the two words can be built up from smaller subproblems by considering the last characters.

Key Insight: If the last characters match, use the solution for the prefixes without these characters. If they don’t match, consider all three possible operations.

Visual State Transition:

  flowchart TD
    A[Start: Empty strings] --> B[Compare chars]
    B --> C{Characters match?}
    C -->|Yes| D[Use diagonal value]
    C -->|No| E[Take minimum of three options]
    D --> F[Fill current cell]
    E --> F
    F --> G{End of strings?}
    G -->|No| B
    G -->|Yes| H[Result: Edit distance]

    style A fill:#e1f5fe
    style H fill:#e8f5e8
    style C fill:#fff3e0

Code Solution:

function minDistance(word1, word2) {
    const m = word1.length, n = word2.length;
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));

    // Initialize base cases
    for (let i = 0; i <= m; i++) dp[i][0] = i;
    for (let j = 0; j <= n; j++) dp[0][j] = j;

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(
                    dp[i - 1][j] + 1,     // Delete
                    dp[i][j - 1] + 1,     // Insert
                    dp[i - 1][j - 1] + 1  // Replace
                );
            }
        }
    }

    return dp[m][n];
}

def min_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Initialize base cases
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(
                    dp[i - 1][j] + 1,     # Delete
                    dp[i][j - 1] + 1,     # Insert
                    dp[i - 1][j - 1] + 1  # Replace
                )

    return dp[m][n]

public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        // Initialize base cases
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(
                        Math.min(dp[i - 1][j] + 1,     // Delete
                                dp[i][j - 1] + 1),    // Insert
                        dp[i - 1][j - 1] + 1          // Replace
                    );
                }
            }
        }

        return dp[m][n];
    }
}

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.length(), n = word2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        // Initialize base cases
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min({
                        dp[i - 1][j] + 1,     // Delete
                        dp[i][j - 1] + 1,     // Insert
                        dp[i - 1][j - 1] + 1  // Replace
                    });
                }
            }
        }

        return dp[m][n];
    }
};

func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    // Initialize base cases
    for i := 0; i <= m; i++ {
        dp[i][0] = i
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = min(
                    min(dp[i-1][j]+1,     // Delete
                        dp[i][j-1]+1),    // Insert
                    dp[i-1][j-1]+1)       // Replace
            }
        }
    }

    return dp[m][n]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

def min_distance(word1, word2)
    m, n = word1.length, word2.length
    dp = Array.new(m + 1) { Array.new(n + 1, 0) }

    # Initialize base cases
    (0..m).each { |i| dp[i][0] = i }
    (0..n).each { |j| dp[0][j] = j }

    (1..m).each do |i|
        (1..n).each do |j|
            if word1[i - 1] == word2[j - 1]
                dp[i][j] = dp[i - 1][j - 1]
            else
                dp[i][j] = [
                    dp[i - 1][j] + 1,     # Delete
                    dp[i][j - 1] + 1,     # Insert
                    dp[i - 1][j - 1] + 1  # Replace
                ].min
            end
        end
    end

    dp[m][n]
end

6. Jump Game II

LeetCode 45 | Difficulty: Medium | Acceptance: 39.7%

Brief: Find the minimum number of jumps needed to reach the last index in an array where each element represents maximum jump length.

Why this pattern?: The minimum jumps to reach position i can be found by considering all previous positions that can reach i.

Key Insight: For each position, update all reachable positions with the minimum jumps needed to reach them.

Visual State Transition:

  graph TD
    A[Position 0] --> B[Position 1]
    A --> C[Position 2]
    A --> D[Position 3]
    B --> E[Position 4]
    C --> E
    C --> F[Position 5]
    D --> F

Code Solution:

function jump(nums) {
    if (nums.length <= 1) return 0;

    const dp = new Array(nums.length).fill(Infinity);
    dp[0] = 0;

    for (let i = 0; i < nums.length; i++) {
        for (let j = 1; j <= nums[i] && i + j < nums.length; j++) {
            dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
        }
    }

    return dp[nums.length - 1];
}

def jump(nums):
    if len(nums) <= 1:
        return 0

    dp = [float('inf')] * len(nums)
    dp[0] = 0

    for i in range(len(nums)):
        for j in range(1, nums[i] + 1):
            if i + j < len(nums):
                dp[i + j] = min(dp[i + j], dp[i] + 1)

    return dp[-1]

public class Solution {
    public int jump(int[] nums) {
        if (nums.length <= 1) return 0;

        int[] dp = new int[nums.length];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 0; i < nums.length; i++) {
            for (int j = 1; j <= nums[i] && i + j < nums.length; j++) {
                dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
            }
        }

        return dp[nums.length - 1];
    }
}

class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size() <= 1) return 0;

        vector<int> dp(nums.size(), INT_MAX);
        dp[0] = 0;

        for (int i = 0; i < nums.size(); i++) {
            for (int j = 1; j <= nums[i] && i + j < nums.size(); j++) {
                dp[i + j] = min(dp[i + j], dp[i] + 1);
            }
        }

        return dp[nums.size() - 1];
    }
};

func jump(nums []int) int {
    if len(nums) <= 1 {
        return 0
    }

    dp := make([]int, len(nums))
    for i := range dp {
        dp[i] = math.MaxInt32
    }
    dp[0] = 0

    for i := 0; i < len(nums); i++ {
        for j := 1; j <= nums[i] && i+j < len(nums); j++ {
            dp[i+j] = min(dp[i+j], dp[i]+1)
        }
    }

    return dp[len(nums)-1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

def jump(nums)
    return 0 if nums.length <= 1

    dp = Array.new(nums.length, Float::INFINITY)
    dp[0] = 0

    (0...nums.length).each do |i|
        (1..nums[i]).each do |j|
            if i + j < nums.length
                dp[i + j] = [dp[i + j], dp[i] + 1].min
            end
        end
    end

    dp[-1]
end

Hard Problems

7. Regular Expression Matching

LeetCode 10 | Difficulty: Hard | Acceptance: 27.9%

Brief: Implement regular expression matching with support for ‘.’ and ‘’ where ‘.’ matches any single character and ‘’ matches zero or more of the preceding element.

Why this pattern?: The matching of pattern p against string s can be broken down into subproblems based on the current characters and whether the next character in p is ‘*’.

Key Insight: When encountering ‘*’, we must consider both zero occurrences (skip the pattern) and one or more occurrences (match current character and continue).

Visual State Transition:

  stateDiagram-v2
    [*] --> Start: Begin matching
    Start --> MatchChar: Single char match
    Start --> ZeroOccur: * with zero occurrence
    Start --> OneOrMore: * with one+ occurrence
    MatchChar --> Start: Continue
    ZeroOccur --> Start: Skip pattern
    OneOrMore --> OneOrMore: Continue matching
    OneOrMore --> Start: Stop matching
    Start --> [*]: End of strings

Code Solution:

function isMatch(s, p) {
    const m = s.length, n = p.length;
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(false));

    dp[0][0] = true; // Empty string matches empty pattern

    // Handle patterns with *
    for (let j = 1; j <= n; j++) {
        if (p[j - 1] === '*') {
            dp[0][j] = dp[0][j - 2]; // Zero occurrence
        }
    }

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[j - 1] === '.' || p[j - 1] === s[i - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p[j - 1] === '*') {
                // Zero occurrence
                dp[i][j] = dp[i][j - 2];
                // One or more occurrence
                if (p[j - 2] === '.' || p[j - 2] === s[i - 1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            }
        }
    }

    return dp[m][n];
}

def is_match(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]

    dp[0][0] = True  # Empty string matches empty pattern

    # Handle patterns with *
    for j in range(1, n + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 2]  # Zero occurrence

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == '.' or p[j - 1] == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            elif p[j - 1] == '*':
                # Zero occurrence
                dp[i][j] = dp[i][j - 2]
                # One or more occurrence
                if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
                    dp[i][j] = dp[i][j] or dp[i - 1][j]

    return dp[m][n]

public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];

        dp[0][0] = true; // Empty string matches empty pattern

        // Handle patterns with *
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2]; // Zero occurrence
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    // Zero occurrence
                    dp[i][j] = dp[i][j - 2];
                    // One or more occurrence
                    if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                }
            }
        }

        return dp[m][n];
    }
}

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));

        dp[0][0] = true; // Empty string matches empty pattern

        // Handle patterns with *
        for (int j = 1; j <= n; j++) {
            if (p[j - 1] == '*') {
                dp[0][j] = dp[0][j - 2]; // Zero occurrence
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == '.' || p[j - 1] == s[i - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p[j - 1] == '*') {
                    // Zero occurrence
                    dp[i][j] = dp[i][j - 2];
                    // One or more occurrence
                    if (p[j - 2] == '.' || p[j - 2] == s[i - 1]) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                }
            }
        }

        return dp[m][n];
    }
};

func isMatch(s string, p string) bool {
    m, n := len(s), len(p)
    dp := make([][]bool, m+1)
    for i := range dp {
        dp[i] = make([]bool, n+1)
    }

    dp[0][0] = true // Empty string matches empty pattern

    // Handle patterns with *
    for j := 1; j <= n; j++ {
        if p[j-1] == '*' {
            dp[0][j] = dp[0][j-2] // Zero occurrence
        }
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if p[j-1] == '.' || p[j-1] == s[i-1] {
                dp[i][j] = dp[i-1][j-1]
            } else if p[j-1] == '*' {
                // Zero occurrence
                dp[i][j] = dp[i][j-2]
                // One or more occurrence
                if p[j-2] == '.' || p[j-2] == s[i-1] {
                    dp[i][j] = dp[i][j] || dp[i-1][j]
                }
            }
        }
    }

    return dp[m][n]
}

def is_match(s, p)
    m, n = s.length, p.length
    dp = Array.new(m + 1) { Array.new(n + 1, false) }

    dp[0][0] = true # Empty string matches empty pattern

    # Handle patterns with *
    (1..n).each do |j|
        if p[j - 1] == '*'
            dp[0][j] = dp[0][j - 2] # Zero occurrence
        end
    end

    (1..m).each do |i|
        (1..n).each do |j|
            if p[j - 1] == '.' || p[j - 1] == s[i - 1]
                dp[i][j] = dp[i - 1][j - 1]
            elsif p[j - 1] == '*'
                # Zero occurrence
                dp[i][j] = dp[i][j - 2]
                # One or more occurrence
                if p[j - 2] == '.' || p[j - 2] == s[i - 1]
                    dp[i][j] = dp[i][j] || dp[i - 1][j]
                end
            end
        end
    end

    dp[m][n]
end

Recommended Study Order

Start with Easy Problems: Climbing Stairs and House Robber to master the basic DP pattern
Move to Medium Problems: Longest Increasing Subsequence, Coin Change, and Jump Game II for more complex state transitions
Tackle Hard Problems: Edit Distance and Regular Expression Matching for advanced 2D DP patterns

Remember: DP problems often have multiple valid solutions. Focus on understanding the recurrence relation over memorizing specific problems. Practice implementing these solutions from scratch to build your problem-solving intuition.