Basic

1. Fibonacci

Finding Nth Fibonacci number

class Solution {
public:
    int fib(int n) {
        if (n <= 1)
            return n;
        vector<int> dp(n + 1);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

2. Climbing Stairs

You are climbing a staircase with n steps. At each move, you can climb either 1 or 2 steps. Return the total number of distinct ways to reach the top.

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2)
            return n;
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

3. Min Cost of Climbing Stairs

You are given an integer array cost, where cost[i] is the cost of stepping on the ith stair. You can climb either 1 or 2 steps at a time, and you may start from step 0 or 1. Return the minimum cost to reach the top.

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n);
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < n; i++) {
            dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]);
        }
        return min(dp[n - 1], dp[n - 2]);
    }
};

4. House Robber

You are given an array nums, where nums[i] is the amount of money in the ith house. You cannot rob two adjacent houses. Return the maximum amount of money you can rob.

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1)
            return nums[0];
        vector<int> dp(n);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);
        }
        return dp[n - 1];
    }
};

Intermediate

1. House Robber II

Houses are arranged in a circle, so the first and last houses are adjacent. Return the maximum amount of money you can rob without robbing two adjacent houses.

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1)
            return nums[0];
        return max(robRange(nums, 0, n - 2),
                   robRange(nums, 1, n - 1));
    }

private:
    int robRange(vector<int>& nums, int l, int r) {
        int prev2 = 0, prev1 = 0;
        for (int i = l; i <= r; i++) {
            int curr = max(prev1, nums[i] + prev2);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
};

2. Coin Change

You are given an array coins representing coin denominations and an integer amount. Return the minimum number of coins needed to make up the amount. If it is not possible, return -1.

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin) {
                    dp[i] = min(dp[i], 1 + dp[i - coin]);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

3. Coins Change (Num ways)

You are given an array coins and an integer amount. Return the number of different combinations that make up the amount. You may use each coin an unlimited number of times.

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
};

4. Longest Palindromic Substring

Given a string s, return the longest substring of s that is a palindrome.

Algorithm:

1. Let n = len(s). Create a 2D table dp[n][n] initialized to false.
2. Keep resIdx = 0 and resLen = 0 for the best answer.
3. For i from n-1 down to 0:
   • For j from i up to n-1:
     • If s[i] == s[j] and (j - i <= 2 OR dp[i+1][j-1] is true):
       • Mark dp[i][j] = true
       • If (j - i + 1) is bigger than resLen, update resIdx and resLen.
4. Return s[resIdx : resIdx + resLen].

class Solution:
    def longestPalindrome(self, s: str) -> str:
        resIdx, resLen = 0, 0
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]):
                    dp[i][j] = True
                    if resLen < (j - i + 1):
                        resIdx = i
                        resLen = j - i + 1

        return s[resIdx : resIdx + resLen]

5. Palindromic Substrings

Given a string s, return the number of substrings within s that are palindromes.

Algorithm:

1. Create a 2D DP table dp[i][j]
   • dp[i][j] = true if substring s[i..j] is a palindrome
2. Initialize a counter res = 0
3. Traverse the string from bottom to top for i
   • This ensures dp[i+1][j-1] is already computed
4. For each (i, j) where j >= i:
   • If s[i] == s[j] AND
     (j - i <= 2 OR dp[i+1][j-1] == true)
     • Mark dp[i][j] = true
     • Increment res
5. Return res

class Solution:
    def countSubstrings(self, s: str) -> int:
        n, res = len(s), 0
        dp = [[False] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]):
                    dp[i][j] = True
                    res += 1

        return res

6. Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of dictionary words.

Example

Input: s = "applepenapple", wordDict = ["apple","pen","ape"]
Output: true

Input: s = "catsincars", wordDict = ["cats","cat","sin","in","car"]
Output: false

Key idea:

• dp[i] means whether the substring s[i:] can be segmented
• If we know the answer for future positions, we can decide the current one
• We reuse already computed results → no recursion, no stack overhead

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * (len(s) + 1)
        dp[len(s)] = True

        for i in range(len(s) - 1, -1, -1):
            for w in wordDict:
                if (i + len(w)) <= len(s) and s[i : i + len(w)] == w:
                    dp[i] = dp[i + len(w)]
                if dp[i]:
                    break

        return dp[0]

7. Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example

Input: nums = [9,1,4,2,3,3,7]
Output: 4

Intuition
A simpler 1D approach: let LIS[i] be the length of the longest increasing subsequence starting at index i. Working from right to left, for each i, we check all j > i. If nums[i] < nums[j], we can extend the subsequence starting at j. We take the maximum extension and add 1 for the current element.

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        LIS = [1] * len(nums)

        for i in range(len(nums) - 1, -1, -1):
            for j in range(i + 1, len(nums)):
                if nums[i] < nums[j]:
                    LIS[i] = max(LIS[i], 1 + LIS[j])
        return max(LIS)

8. Partition Equal Subset Sum

You are given an array of positive integers nums. Return true if you can partition the array into two subsets, subset1 and subset2 where sum(subset1) == sum(subset2).Otherwise, return false.

Intuition

At any point:

• dp contains all subset sums that can be formed using the processed numbers.
  For each new number:
• Every existing sum t can either:
  • Stay the same (don’t pick the number)
  • Become t + num (pick the number)
    If at any time we form target, we can stop early and return True.

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums) % 2:
            return False

        dp = set()
        dp.add(0)
        target =  sum(nums) // 2
        for i in range(len(nums)-1, -1, -1):
            nxtdp = set()
            for t in dp:
                if (t + nums[i]) == target:
                    return True
                nxtdp.add(t + nums[i])
                nxtdp.add(t)
            dp = nxtdp
        return False

9. Longest Common SubSequence

Given two strings text1 and text2, return the length of the longest common subsequence between the two strings if one exists, otherwise return 0.

Intuition

Instead of starting from the beginning and recursing forward, we can fill a 2D table iteratively from the end. The value dp[i][j] represents the LCS length for substrings text1[i:] and text2[j:]. By processing indices in reverse order, we ensure that when we compute dp[i][j], the values we depend on (dp[i+1][j+1], dp[i+1][j], dp[i][j+1]) are already computed.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0] * (len(text2) + 1) for _ 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][j + 1], dp[i + 1][j])
        return dp[0][0]