Dynamic Programming

Spot It

• "Count the number of ways to..."
• "Minimum/maximum cost/steps to reach..."
• "Can you achieve X?" (often boolean DP)
• Overlapping subproblems + optimal substructure = DP

Greedy vs DP: If past choices constrain future options and overlap → DP. If local optimum always leads to global optimum → Greedy.

---

Approach Decision

Can I define the answer as f(index)?
├── Yes — try 1D DP
│   ├── Current state depends only on adjacent? → O(1) space possible
│   └── Needs range/previous window? → O(N) space
└── Two variables (two strings, grid)? → 2D DP
    └── Usually O(M×N) space, sometimes O(N) row

Top-Down (memoization): natural if recursion is obvious → add @cache or dp dict
Bottom-Up (tabulation): usually faster in practice, no recursion overhead

---

Interview Pattern: Longest Common Subsequence (LCS)

Use when: Two strings/arrays, find longest common subsequence, edit distance, shortest common supersequence.

# LC 1143 — Longest Common Subsequence
def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]    # chars match — extend diagonal
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])   # skip one char from either

    return dp[m][n]

# LC 72 — Edit Distance (LCS variant)
def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): dp[i][0] = i   # delete all of word1
    for j in range(n + 1): dp[0][j] = j   # insert all of word2

    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]                           # no op needed
            else:
                dp[i][j] = 1 + min(dp[i-1][j],    # delete from word1
                                   dp[i][j-1],    # insert into word1
                                   dp[i-1][j-1])  # replace

    return dp[m][n]

---

Interview Pattern: 0/1 Knapsack

Use when: Each item usable at most once. "Can we partition", "subset sum", "target sum".

# LC 416 — Partition Equal Subset Sum
def canPartition(nums):
    total = sum(nums)
    if total % 2: return False
    target = total // 2

    dp = {0}  # set of reachable sums
    for num in nums:
        dp = dp | {s + num for s in dp}   # add num to every reachable sum
        if target in dp: return True
    return False

# General 0/1 Knapsack (tabulation)
def knapsack01(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i-1][w]   # don't take item i
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w], values[i-1] + dp[i-1][w - weights[i-1]])

    return dp[n][capacity]

# Space-optimized: iterate w in reverse to avoid using same item twice
def knapsack01_1d(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for w in range(capacity, weights[i] - 1, -1):   # reverse!
            dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
    return dp[capacity]

Key: Reverse inner loop in 1D version — prevents using item i more than once.

---

Interview Pattern: Unbounded Knapsack

Use when: Each item usable unlimited times. Coin change, rod cutting.

# LC 322 — Coin Change (min coins)
def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], 1 + dp[a - c])
    return dp[amount] if dp[amount] != float('inf') else -1

# LC 518 — Coin Change II (count ways)
def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in coins:                        # outer loop = items
        for a in range(c, amount + 1):    # forward! — reuse same coin
            dp[a] += dp[a - c]
    return dp[amount]

Key difference from 0/1: Forward inner loop (not reverse) — allows reusing the same coin.

---

Interview Pattern: Longest Increasing Subsequence (LIS)

Use when: Strictly increasing subsequence, patience sorting, box stacking.

# LC 300 — LIS — O(N²) DP
def lengthOfLIS(nums):
    dp = [1] * len(nums)   # every element is a length-1 LIS by itself
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# O(N log N) — binary search + patience sort (senior bar)
from bisect import bisect_left

def lengthOfLIS_fast(nums):
    tails = []   # tails[i] = smallest tail of LIS of length i+1
    for n in nums:
        pos = bisect_left(tails, n)
        if pos == len(tails):
            tails.append(n)
        else:
            tails[pos] = n    # replace — maintains smallest tail
    return len(tails)

Senior note: O(N log N) tails array is NOT the actual LIS — it only gives the length. To reconstruct, need a parent array.

---

Interview Pattern: Palindromic DP

# LC 647 — Count Palindromic Substrings
def countSubstrings(s):
    count = 0
    for center in range(2 * len(s) - 1):     # expand from each center
        left = center // 2
        right = left + center % 2
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1; right += 1
    return count

# LC 5 — Longest Palindromic Substring
def longestPalindrome(s):
    res = ""
    for center in range(2 * len(s) - 1):
        left, right = center // 2, center // 2 + center % 2
        while left >= 0 and right < len(s) and s[left] == s[right]:
            if right - left + 1 > len(res):
                res = s[left:right+1]
            left -= 1; right += 1
    return res

Expand-from-center beats 2D DP: O(N) space, O(N²) time — same complexity but simpler code.

---

Quick Reference

---

Problem Table

---

Full Problem Walkthroughs

Raw notes below — full memoization + tabulation + space-optimized implementations.

---

There are two approaches to solve any DP problem:

1. Tabulation - Bottom up approach
   • The problem is solved in the direction of solving the base cases to the main problem
2. Memoization - Top down approach
   •  The problem is solved in the direction of the main problem to the base cases.

Problem Contest: https://atcoder.jp/contests/dp

1D Dynamic Programming

How to Identify a DP Problem?

• If problem asks following:
  • Count total number of ways
  • Given multiple ways of doing a task, which way will give the minimum or the maximum output.
• First try to solve problem using the recursion and then convert it to DP

Steps to solve any DP problem:

1. Try to represent problem in terms of index
2. Try all possible choices/ways at every index according to the problem statement.
3. If the question states
   • Count all the ways - return sum of all choices/ways.
   • Find maximum/minimum- return the choice/way with maximum/minimum output.

Problems

Climbing Stairs

• Link: https://leetcode.com/problems/climbing-stairs/description/

Frog Jump

Problem Statement:

• Link: https://takeuforward.org/data-structure/dynamic-programming-frog-jump-dp-3/
• Given a number of stairs and a frog, the frog wants to climb from the 0th stair to the (N-1)th stair. At a time the frog can climb either one or two steps.
• A height[N] array is also given. Whenever the frog jumps from a stair i to stair j, the energy consumed in the jump is abs(height[i]- height[j]), where abs() means the absolute difference.
• We need to return the minimum energy that can be used by the frog to jump from stair 0 to stair N-1.

Memoization Approach (Top Down):

def frogJump(n: int, heights: List[int]) -> int:
    dp = [0] + [-1] * (n - 1)

    def dfs(idx):
        if idx == 0:
            return 0
        if idx == 1:
            dp[idx] = dfs(idx-1) + abs(heights[idx] - heights[idx - 1])
            return dp[idx]
        if dp[idx] != -1:
            return dp[idx]
        left = dfs(idx-1) + abs(heights[idx] - heights[idx - 1])
        right = dfs(idx-2) + abs(heights[idx] - heights[idx - 2])
        dp[idx] = min(left, right)
        return dp[idx]
    dfs(n-1)
    return dp[n-1]

Tabular Approach (Bottom Up):

def frogJump(n: int, heights: List[int]) -> int:
    dp = [-1] * (n)
    dp[0] = 0
    dp[1] = abs(heights[1] - heights[0])

    for i in range(2, n):
        dp[i] = min(
                    dp[i-1] + abs(heights[i-1] - heights[i]), 
                    dp[i-2] + abs(heights[i-2] - heights[i])
                ) 
    return dp[-1]

Tabular Approach Space Optimized (Bottom Up):

def frogJump(n: int, heights: List[int]) -> int:
    dp = [-1] * (n)
    dp_0 = 0
    dp_1 = abs(heights[1] - heights[0])

    for i in range(2, n):
        dp_i = min(
                    dp_0 + abs(heights[i-1] - heights[i]), 
                    dp_1 + abs(heights[i-2] - heights[i])
                )
        dp_0 = dp_1
        dp_1 = dp_i
    return dp_1

Follow up problem: https://atcoder.jp/contests/dp/tasks/dp_b If instead of 2 jumps i.e i+1 and i+2, there are k jumps i+1, i+2, ..., i+k. How to solve this?

Tabular Solution:

def frogJump(n: int, k: int, heights: List[int]) -> int:
	dp = [-1] * n
	dp[0] = 0
	
	for i in range(1, n):
	  min_val = float("inf")
	  for j in range(i-1, max(i-k-1, -1), -1):
	    curr_val = dp[j] + abs(stones[i] - stones[j])
	    if curr_val < min_val:
	      min_val = curr_val
	  dp[i] = min_val
	return dp[n-1]

Maximum sum of non-adjacent elements | House Robber

Problem Statement:

• Link: https://leetcode.com/problems/house-robber/description/

Memoization Approach (Top Down):

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [-1] * n
        def dfs(idx):
            if idx == 0:
                dp[idx] = nums[idx]
                return nums[idx]
            if idx < 0:
                return 0
            if dp[idx] != -1:
                return dp[idx]
            left = dfs(idx-2) + nums[idx]
            right = dfs(idx-1)
            dp[idx] = max(left, right)
            return dp[idx]
        dfs(n-1)
        return dp[n-1]

Tabular Approach (Bottom Up):

class Solution:
	def rob(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        for i in range(1, n):
            pick = nums[i]
            if i > 1:
                pick += dp[i-2]
            not_pick = dp[i-1]
            dp[i] = max(pick, not_pick)
        return dp[n-1]

Tabular Approach Space Optimized (Bottom Up):

class Solution:
	def rob(self, nums: List[int]) -> int:
        n = len(nums)
        adj_house = nums[0]
        non_adj = 0
        for i in range(1, n):
            pick = nums[i] + non_adj
            not_pick = adj_house
            curr_pick = max(pick, not_pick)
            non_adj = adj_house
            adj_house = curr_pick
        return adj_house

House Robber Part-2

Problem Statement:

• You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system 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.

Solution Approach:

• We can use the same code from the House Robber part 1 and just run the code for including the first and removing last element or else adding last and removing first element and take the maximum value from both of them.

Memoization Approach (Top Down):

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        dp = [-1] * n
        def dfs(idx, low):
            if idx == low:
                dp[idx] = nums[idx]
                return dp[idx]
            if idx < low:
                return 0
            if dp[idx] != -1:
                return dp[idx]
            left = dfs(idx-2, low) + nums[idx]
            right = dfs(idx-1, low)
            dp[idx] = max(left, right)
            return dp[idx]
        dp_n = dfs(n-1, 1)
        dp = [-1] * n
        dp_n_1 = dfs(n-2, 0)
        return max(dp_n, dp_n_1)

Tabular Approach Space Optimized (Bottom Up):

class Solution:
	def dfs(self, houses):
        adj_house = houses[0]
        non_adj = 0
        for i in range(1, len(houses)):
            curr_pick = max(non_adj + houses[i], adj_house)
            non_adj = adj_house
            adj_house = curr_pick
        return adj_house

    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return nums[0]
        return max(self.dfs(nums[:-1]), self.dfs(nums[1:]))

2D Dynamic Programming

Problems:

Ninja Training:

Problem Statement:

• Ninja is planing this ‘N’ days-long training schedule.
• Each day, he can perform any one of these three activities. (Running, Fighting Practice or Learning New Moves).
• Each activity has some merit points on each day. As Ninja has to improve all his skills, he can’t do the same activity in two consecutive days. Can you help Ninja find out the maximum merit points Ninja can earn?
• You are given a 2D array of size N * 3 ‘POINTS’ with the points corresponding to each day and activity. Your task is to calculate the maximum number of merit points that Ninja can earn.

Memoization Approach (Top Down): Time : O((N * 4) * 3)) Space: O(N) + O(N * 4)

from typing import *


def dfs(day, last, points, dp):
    if day == 0:
        maxi = 0
        for i in range(3):
            if i != last:
                maxi = max(maxi, points[0][i])
        return maxi
    if dp[day][last] != -1:
        return dp[day][last]
    maxi = 0
    for i in range(3):
        if i != last:
            point = points[day][i] + dfs(day-1, i, points, dp)
            maxi = max(maxi, point)
    dp[day][last] = maxi
    return maxi

def ninjaTraining(n: int, points: List[List[int]]) -> int:
    dp = [[-1] * 4 for _ in range(n)]
    return dfs(n - 1, 3, points, dp)

Tabular Approach (Bottom Up): Time : O((N * 4) * 3)) Space: O(N * 4)

def ninjaTraining(n: int, points: List[List[int]]) -> int:
    dp = [[-1] * 4 for _ in range(n)]
    dp[0][0] = max(points[0][1], points[0][2])
    dp[0][1] = max(points[0][0], points[0][2])
    dp[0][2] = max(points[0][0], points[0][1])
    dp[0][3] = max(points[0][0], max(points[0][1], points[0][2]))

    for i in range(1, n):
        for last in range(4):
            maxi = 0
            for current in range(3):
                if current != last:
                    point = points[i][current] + dp[i-1][current]
                    maxi = max(point, maxi)
            dp[i][last] = maxi
    return dp[n-1][3]

Tabular Approach Space Optimized (Bottom Up): Time : O((N * 3) * 3)) Space: O(1)

def ninjaTraining(n: int, points: List[List[int]]) -> int:
    dp = [-1] * 3
    dp[0] = max(points[0][1], points[0][2])
    dp[1] = max(points[0][0], points[0][2])
    dp[2] = max(points[0][0], points[0][1])
    # dp[3] = max(points[0][0], max(points[0][1], points[0][2]))

    for i in range(1, n):
        temp = [0] * 3
        for last in range(3):
            for current in range(3):
                if current != last:
                    point = points[i][current] + dp[current]
                    temp[last] = max(point, temp[last])
        dp = temp
    return max(dp[0], max(dp[1], dp[2]))

DP on Grid problems:

Unique Paths:

Problem Statement:

• There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
• Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Memoization Approach (Top Down): Time : O(N * M) Space: O(N * M) + O(N * M)

class Solution:
    def dfs(self, i, j, dp):
        if (i, j) == (0, 0):
            return 1
        if dp[i][j] != -1:
            return dp[i][j]
        ans = 0
        if i-1 >= 0:
            ans += self.dfs(i-1, j, dp) 
        if j -1 >= 0:
            ans += self.dfs(i, j - 1, dp)
        dp[i][j] = ans
        return ans 
    
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[-1] * n for _ in range(m)] 
        return self.dfs(m-1, n-1, dp)

Tabular Approach (Bottom Up): Time : O(N * M) Space: O(N * M)

class Solution:
	def uniquePaths(self, m: int, n: int) -> int:
        dp = [[-1] * n for _ in range(m)] 
        dp[0][0] = 1
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue
                up = 0
                if i > 0:
                    up = dp[i-1][j]
                left = 0
                if j > 0:
                    left = dp[i][j-1]
                dp[i][j] = up + left
        return dp[m-1][n-1]

Tabular Approach Space Optimized (Bottom Up): Time : O(N * M) Space: O(1)

class Solution:
	def uniquePaths(self, m: int, n: int) -> int:
        prev = [0] * n
        for i in range(m):
	        temp = [0] * n
            for j in range(n):
                if i == 0 and j == 0:
	                temp[j] = 1
                    continue
                up = 0
                if i > 0:
                    up = prev[j]
                left = 0
                if j > 0:
                    left = temp[j-1]
                temp[j] = up + left
            prev = temp
        return prev[n-1]

Unique Paths 2:

Problem Statement:

• You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
• An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.
• Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Memoization Approach (Top Down): Time : O(N * M) Space: O(N * M) + O(N * M)

class Solution:
    def dfs(self, i, j, dp, grid):
        if grid[i][j] == 1:
            return 0
        if (i, j) == (0, 0):
            return 1
        if dp[i][j] != -1:
            return dp[i][j]
        ans = 0
        if i-1 >= 0:
            ans += self.dfs(i-1, j, dp, grid) 
        if j -1 >= 0:
            ans += self.dfs(i, j - 1, dp, grid)
        dp[i][j] = ans
        return ans
    
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
		m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        dp = [[-1] * n for _ in range(m)] 
        return self.dfs(m-1, n-1, dp, obstacleGrid)

Tabular Approach (Bottom Up): Time : O(N * M) Space: O(N * M)

class Solution:
	def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
		m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        dp = [[-1] * n for _ in range(m)] 
        dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                    continue
                up = 0
                if i > 0:
                    up = dp[i-1][j]
                left = 0
                if j > 0:
                    left = dp[i][j-1]
                dp[i][j] = up + left
        return dp[m-1][n-1]

Tabular Approach Space Optimized (Bottom Up): Time : O(N * M) Space: O(1)

class Solution:
	def uniquePaths(self, m: int, n: int) -> int:
        prev = [0] * n
        for i in range(m):
	        temp = [0] * n
            for j in range(n):
                if i == 0 and j == 0:
	                temp[j] = 1
                    continue
                up = 0
                if i > 0:
                    up = prev[j]
                left = 0
                if j > 0:
                    left = temp[j-1]
                temp[j] = up + left
            prev = temp
        return prev[n-1]