Dynamic Programming

1D Dynamic Programming

Top Down

Memoization or Caching
Moving top -> down on our decision tree

def fib(self, n: int) -> int:
	memo = {0: 0, 1: 1}

	def bruteForce(n):
		if n <= 1:
			return n
		if n in memo:
			return memo[n]
		memo[n] = bruteForce(n-1) + bruteForce(n-2)
		return memo[n]

	return bruteForce(n)

Bottom Up

Start at the bottom of the tree and move up
No recursion used at all
True Dynamic Programming
Start at the base case and calculate up

def fib(self, n: int) -> int:
	if n <= 1:
		return n
	
	a, b = 0, 1

	for _ in range(2, n):
		a, b = b, a + b
	return a + b

2D Dynamic Programming

Palindrome

Do not follow the regular DP steps
- Recursive DFS
- Memoization
- Top down or Bottom up DP optimization
Still DP problem
In general sense, sub problem does not help us figure out whether the outer problem is palindrome or not. Not at least using the two pointer technique.
The for loop is needed to iterate over each character in the string, treating each one as a potential center of a palindrome. In palindrome checking, a palindrome can either have:

• Odd length: where there is a single character at the center (e.g., “racecar”, center is ‘e’).
• Even length: where there are two center characters (e.g., “abba”, centers are ‘bb’).

Since a palindrome can potentially start from any index in the string, you need to check around each character (odd-length palindromes) and between each pair of characters (even-length palindromes). The for loop ensures that every possible center in the string is examined for both types of palindromes.

Without the for loop, the solution would not explore all possible centers and would miss some palindromic substrings.

def longestPalindrome(self, s: str) -> str:
	longest = 0  # Length of the longest palindrome found so far
	leftMost = 0  # Left index of the longest palindrome
	rightMost = 0  # Right index of the longest palindrome

	for i in range(len(s)):
		# Check for even-length palindromes (e.g., "baab")
		l, r = i, i + 1  # Start with two middle points
		while l >= 0 and r < len(s) and s[l] == s[r]:  # Expand outwards while characters match
			if r - l + 1 > longest:  # Update if the current palindrome is longer
				longest = (r - l + 1)
				leftMost = l
				rightMost = r
			l -= 1  # Move left pointer outwards
			r += 1  # Move right pointer outwards

		# Check for odd-length palindromes (e.g., "babad")
		l, r = i, i  # Start with one middle point
		while l >= 0 and r < len(s) and s[l] == s[r]:  # Expand outwards while characters match
			if r - l + 1 > longest:  # Update if the current palindrome is longer
				longest = (r - l + 1)
				leftMost = l
				rightMost = r
			l -= 1  # Move left pointer outwards
			r += 1  # Move right pointer outwards

	# Return the substring from the stored left and right indices
	return s[leftMost:rightMost + 1]

0/1 Knapsack

Have a fixed capacity
Have some items
Called 0/1 because for each item you can have 0 or 1 item of it

Memoization

def dfs(profit, weight, capacity):
	return dfsHelper(0, profit, weight, capacity)

@cache
def dfsHelper(i, profit, weight, capacity):
	if i == len(profit):
		return 0

	# Skip item i - Incrementing the index but not reducing capacity
	maxProfit = dfsHelper(i + 1, profit, weight, capacity)

	# Include item i - Incrementing the index but reducing the capactiy
	newCap = capacity - weight[i]
	if newCap >= 0:
		newProfit = profit[i] + dfsHelper(i + 1, profit, weight, newCap)
		# Compute the max
		maxProfit = max(maxProfit, newProfit)
	
	return maxProfit

True DP Solution

def knapSack(self, maxWeight, weights, values):
    numItems, capacity = len(values), maxWeight
    # dp[i][j] will store the maximum value for the first i items with a capacity of j
    dp = [[0] * (capacity + 1) for _ in range(numItems)]

    # Initialize the first column (0 capacity means 0 value)
    for i in range(numItems):
        dp[i][0] = 0

    # Initialize the first row (only one item can be chosen)
    for currCapacity in range(capacity + 1):
        dp[0][currCapacity] = values[0] if currCapacity >= weights[0] else 0

    # Fill the dp table by considering each item and capacity
    for item in range(1, numItems):
        for currCapacity in range(1, capacity + 1):
            # Case 1: Don't include the current item
            maxProfitWithoutCurrent = dp[item - 1][currCapacity]

            # Case 2: Include the current item (only if it fits)
            if currCapacity - weights[item] >= 0:
                maxProfitWithCurrent = values[item] + dp[item - 1][currCapacity - weights[item]]
                # Take the maximum of including or not including the current item
                dp[item][currCapacity] = max(maxProfitWithoutCurrent, maxProfitWithCurrent)
            else:
                # If current item can't be included, carry forward the previous profit
                dp[item][currCapacity] = maxProfitWithoutCurrent

    # The answer will be the maximum value for all items with the full capacity
    return dp[numItems - 1][capacity]

Unbounded Knapsack

First decision is to choose the item and not increment the index
Second decision is to skip the item but increment the index
Brute force time complexity is $O (2^{C})$ where C is capacity because you can choose an item any number of times
Memoized time complexity is the same as bounded 0/1 knapsack at $O (n * c)$

Memoization

def dfs(profit, weight, capacity):
	return dfsHelper(0, profit, weight, capacity)

@cache
def dfsHelper(i, profit, weight, capacity):
	if i == len(profit):
		return 0

	# Skip item i - Incrementing the index but not reducing capacity
	maxProfit = dfsHelper(i + 1, profit, weight, capacity)

	# NOT INCREMENTING i is the only diff between bounded and unbounded
	# Include item i - NOT incrementing the index but reducing the capactiy
	newCap = capacity - weight[i]
	if newCap >= 0:
		newProfit = profit[i] + dfsHelper(i, profit, weight, newCap)
		# Compute the max
		maxProfit = max(maxProfit, newProfit)
	
	return maxProfit

True DP

def knapSack(self, maxWeight, weights, values):
    numItems, capacity = len(values), maxWeight
    # dp[i][j] will store the maximum value for the first i items with a capacity of j
    dp = [[0] * (capacity + 1) for _ in range(numItems)]

    # Initialize the first column (0 capacity means 0 value)
    for i in range(numItems):
        dp[i][0] = 0

    # Initialize the first row (only one item can be chosen)
    for currCapacity in range(capacity + 1):
        dp[0][currCapacity] = values[0] if currCapacity >= weights[0] else 0

    # Fill the dp table by considering each item and capacity
    for item in range(1, numItems):
        for currCapacity in range(1, capacity + 1):
            # Case 1: Don't include the current item
            maxProfitWithoutCurrent = dp[item - 1][currCapacity]

            # Case 2: Include the current item (only if it fits)
            if currCapacity - weights[item] >= 0:
	            ## DID NOT LOOK FOR PREVIOUS ITEM's value
                maxProfitWithCurrent = values[item] + dp[item][currCapacity - weights[item]]
                # Take the maximum of including or not including the current item
                dp[item][currCapacity] = max(maxProfitWithoutCurrent, maxProfitWithCurrent)
            else:
                # If current item can't be included, carry forward the previous profit
                dp[item][currCapacity] = maxProfitWithoutCurrent

    # The answer will be the maximum value for all items with the full capacity
    return dp[numItems - 1][capacity]

Most Optimized with Memory

def optimizedDp(profit, weight, capacity):
	N, M = len(profit), capacity
	dp = [0] * (M + 1) # only creating one row

	for i in range(N):
		curRow = [0] * (M + 1) # creating a temp row
		for c in range(1, M + 1):
			skip = dp[c]
			include = 0
			if c - weight[i] >= 0:
				include = profit[i] + curRow[c - weight[i]]
			curRow[c] = max(include, skip)
		dp = curRow
	return dp[M]

Longest Common Subsequence

Word 2 formed from the same letters of Word 1
Basically can remove some letters from Word 1
The relative ordering matters
E.g. ABC -> AC is a subsequence but CA is not