DSA — Techniques

Dynamic Programming

Break problems into overlapping subproblems, solve each once, store results. Converts exponential → polynomial time.

— min read
OptimalSubstructure
OverlappingSubproblems
Memoiz.Top-Down
Tabul.Bottom-Up
✓FAANG Core
// LONGEST COMMON SUBSEQUENCE TABLE FILL
Press Run to fill the DP table step-by-step
How It Works
Python Code
Key Patterns
Quiz
Practice
01
Identify Subproblems
What smaller version of the problem feeds into larger?
dp[i][j] depends on dp[i-1][j-1] etc.
02
Recurrence Relation
Write the formula that builds each answer from sub-answers.
dp[i][j] = dp[i-1][j-1]+1 if match
03
Base Cases
Initialize dp table boundaries (usually 0s).
dp[0][*] = dp[*][0] = 0
04
Fill Order
Ensure subproblems are solved before you need them.
fill row by row
python 
# LCS — Longest Common Subsequence
def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]
1D DP
Linear
Fibonacci, Climbing Stairs, House Robber
2D DP
Grid/String
LCS, Edit Distance, Knapsack
Interval DP
Range
Matrix Chain Multiplication, Burst Balloons
Bitmask DP
Subset
Travelling Salesman, subset problems
What distinguishes DP from plain recursion?
Progress 0 / 14 solved
14 problems · 8 PBC · 6 Startup
#119 0/1 Knapsack Problem Amazon, Google PBC →
#120 Longest Increasing Subsequence Amazon PBC →
#121 Longest Common Subsequence Google, Microsoft PBC →
#122 Word Break Meta, Amazon PBC →
#123 Coin Change Google PBC →
#124 Decode Ways Google, Amazon PBC →
#125 Unique Paths with Obstacles Microsoft PBC →
#126 Rod Cutting Google PBC →
#129 Jump Game Zepto STARTUP →
#131 Climbing Stairs Swiggy STARTUP →
#132 House Robber Niyo STARTUP →
#133 Minimum Cost Climbing Stairs Meesho STARTUP →
#134 Minimum Path Sum Ola STARTUP →
#145 Jump Game II Zepto STARTUP →
← Recursion