Java Notes

Dynamic Programming in Java

Complete guide to Dynamic Programming in Java covering memoization, tabulation, classical DP problems (Fibonacci, Knapsack, LCS, LIS, Coin Change), time/space optimization, and interview patterns.

What is Dynamic Programming?

Dynamic Programming (DP) is an algorithmic technique that solves complex problems by breaking them down into simpler overlapping subproblems, solving each subproblem only once, and storing the results for future use. It transforms exponential-time recursive solutions into polynomial-time iterative (or memoized) solutions.

The Two Key Properties

For a problem to be solvable with DP, it must have:

1. Overlapping Subproblems: The same subproblems are solved multiple times during recursion. DP stores (caches) these results to avoid redundant computation.

2. Optimal Substructure: The optimal solution to the problem can be constructed from optimal solutions of its subproblems.

Analogy

Imagine you're asked: "What's 1+1+1+1+1+1+1+1+1+1?"

You count: "10." Now someone adds "+1" to the end. You don't recount from scratch — you remember the previous answer (10) and add 1 → 11.

That's Dynamic Programming: remembering past results to avoid recomputation.

Two Approaches to DP

1. Top-Down (Memoization)

Start with the original problem and recursively break it down
Use a cache (array or HashMap) to store results of subproblems
When a subproblem is encountered again, return the cached result
Natural extension of recursive thinking

2. Bottom-Up (Tabulation)

Start with the smallest subproblems and build up to the solution
Use a table (array) to store results iteratively
No recursion — avoids stack overflow
Usually more space-efficient (can sometimes reduce dimensions)

Fibonacci — The Classic DP Example

Pure Recursion (Exponential — BAD)

java example

public class FibonacciRecursive {
    static int fib(int n) {
        if (n <= 1) return n;
        return fib(n - 1) + fib(n - 2); // Recomputes same values!
    }
    
    public static void main(String[] args) {
        System.out.println("fib(10) = " + fib(10));
        System.out.println("fib(20) = " + fib(20));
        // fib(50) would take MINUTES — exponential time!
    }
}

Output

fib(10) = 55
fib(20) = 6765

Problem: fib(5) computes fib(3) twice, fib(2) three times, etc. Time: O(2^n).

Recursion Tree for fib(5):

Example

fib(5) / \ fib(4) fib(3) ← fib(3) computed TWICE / \ / \ fib(3) fib(2) fib(2) fib(1) ← fib(2) computed THREE times / \ / \ / \ fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) / \ fib(1) fib(0)

Top-Down with Memoization (O(n))

Example

public class FibonacciMemoization { static int[] memo; static int fib(int n) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; // Already computed! memo[n] = fib(n - 1) + fib(n - 2); return memo[n]; } public static void main(String[] args) { int n = 40; memo = new int[n + 1]; java.util.Arrays.fill(memo, -1); System.out.println("fib(" + n + ") = " + fib(n)); // Print first 15 Fibonacci numbers memo = new int[15]; java.util.Arrays.fill(memo, -1); System.out.print("First 15: "); for (int i = 0; i < 15; i++) { System.out.print(fib(i) + " "); } System.out.println(); } }

Output

fib(40) = 102334155
First 15: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

Time: O(n) — each subproblem computed once. Space: O(n) — memo array + recursion stack.

Bottom-Up Tabulation (O(n) time, O(n) space)

Example

public class FibonacciTabulation { static int fib(int n) { if (n <= 1) return n; int[] dp = new int[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]; } public static void main(String[] args) { System.out.println("fib(10) = " + fib(10)); System.out.println("fib(40) = " + fib(40)); System.out.println("fib(50) = " + fib(50)); } }

Output

fib(10) = 55
fib(40) = 102334155
fib(50) = 1264937032

Space-Optimized (O(1) space)

Since each Fibonacci value only depends on the previous two, we don't need the entire array:

Example

public class FibonacciOptimized { static int fib(int n) { if (n <= 1) return n; int prev2 = 0, prev1 = 1; for (int i = 2; i <= n; i++) { int current = prev1 + prev2; prev2 = prev1; prev1 = current; } return prev1; } public static void main(String[] args) { for (int i = 0; i <= 15; i++) { System.out.print(fib(i) + " "); } System.out.println(); } }

Output

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

Time: O(n), Space: O(1) — optimal!

Climbing Stairs Problem

Problem: You can climb 1 or 2 stairs at a time. How many distinct ways to reach step n?

Example

public class ClimbingStairs { public static int climbStairs(int n) { if (n <= 2) return n; int[] dp = new int[n + 1]; dp[1] = 1; // 1 way to reach step 1 dp[2] = 2; // 2 ways to reach step 2 (1+1 or 2) for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; // Come from step i-1 or i-2 } return dp[n]; } public static void main(String[] args) { for (int n = 1; n <= 10; n++) { System.out.println("Steps " + n + ": " + climbStairs(n) + " ways"); } } }

Output

Steps 1: 1 ways
Steps 2: 2 ways
Steps 3: 3 ways
Steps 4: 5 ways
Steps 5: 8 ways
Steps 6: 13 ways
Steps 7: 21 ways
Steps 8: 34 ways
Steps 9: 55 ways
Steps 10: 89 ways

Dry Run for n=4:

Example

dp[1] = 1 (just take 1 step) dp[2] = 2 (1+1 or 2) dp[3] = dp[2] + dp[1] = 2 + 1 = 3 (1+1+1, 1+2, 2+1) dp[4] = dp[3] + dp[2] = 3 + 2 = 5 (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)

0/1 Knapsack Problem

Problem: Given n items with weights and values, and a knapsack capacity W, find the maximum value you can carry without exceeding the weight limit. Each item can be included at most once.

Example

public class Knapsack01 { public static int knapsack(int[] weights, int[] values, int W) { int n = weights.length; int[][] dp = new int[n + 1][W + 1]; // dp[i][w] = max value using first i items with capacity w for (int i = 1; i <= n; i++) { for (int w = 0; w <= W; w++) { // Option 1: Don't include item i dp[i][w] = dp[i - 1][w]; // Option 2: Include item i (if it fits) if (weights[i - 1] <= w) { dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]); } } } return dp[n][W]; } public static void main(String[] args) { int[] weights = {2, 3, 4, 5}; int[] values = {3, 4, 5, 6}; int W = 8; System.out.println("Items:"); for (int i = 0; i < weights.length; i++) { System.out.println(" Item " + (i+1) + ": weight=" + weights[i] + ", value=" + values[i]); } System.out.println("Knapsack capacity: " + W); System.out.println("Maximum value: " + knapsack(weights, values, W)); } }

Output

Items:
  Item 1: weight=2, value=3
  Item 2: weight=3, value=4
  Item 3: weight=4, value=5
  Item 4: weight=5, value=6
Maximum value: 10

Time: O(n × W), Space: O(n × W)

Dry Run (partial DP table):

i=0	0 0 0 0 0 0 0 0 0
i=1	0 0 3 3 3 3 3 3 3
i=2	0 0 3 4 4 7 7 7 7
i=3	0 0 3 4 5 7 8 9 9
i=4	0 0 3 4 5 7 8 9 10

Longest Common Subsequence (LCS)

Problem: Find the length of the longest subsequence common to two strings.

Example

public class LongestCommonSubsequence { public static int lcs(String s1, String s2) { int m = s1.length(), n = s2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s1.charAt(i - 1) == s2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; // Characters match } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // Take max } } } return dp[m][n]; } public static void main(String[] args) { String s1 = "ABCBDAB"; String s2 = "BDCAB"; System.out.println("String 1: " + s1); System.out.println("String 2: " + s2); System.out.println("LCS length: " + lcs(s1, s2)); // LCS is "BCAB" (length 4) } }

Output

String 1: ABCBDAB
String 2: BDCAB
LCS length: 4

Time: O(m × n), Space: O(m × n)

Coin Change Problem

Problem: Given coins of different denominations and a total amount, find the minimum number of coins needed.

Example

import java.util.Arrays; public class CoinChange { public static int minCoins(int[] coins, int amount) { int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 1); // Initialize to impossible value dp[0] = 0; // 0 coins needed for amount 0 for (int i = 1; i <= amount; i++) { for (int coin : coins) { if (coin <= i) { dp[i] = Math.min(dp[i], dp[i - coin] + 1); } } } return dp[amount] > amount ? -1 : dp[amount]; } public static void main(String[] args) { int[] coins = {1, 5, 10, 25}; int[] amounts = {11, 30, 7, 0}; System.out.println("Coins: " + Arrays.toString(coins)); for (int amount : amounts) { int result = minCoins(coins, amount); System.out.println("Amount " + amount + " → Min coins: " + result); } } }

Output

Coins: [1, 5, 10, 25]
Amount 11 → Min coins: 2
Amount 30 → Min coins: 2
Amount 7 → Min coins: 3
Amount 0 → Min coins: 0

Dry Run for amount=11, coins=[1,5,10,25]:

Example

dp[0]=0, dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=4, dp[5]=1 dp[6]=2, dp[7]=3, dp[8]=4, dp[9]=5, dp[10]=1, dp[11]=2 Answer: dp[11] = 2 (one 10 + one 1, or two 5s + one 1)

Longest Increasing Subsequence (LIS)

Example

import java.util.Arrays; public class LongestIncreasingSubsequence { public static int lis(int[] arr) { int n = arr.length; int[] dp = new int[n]; Arrays.fill(dp, 1); // Each element is a subsequence of length 1 int maxLength = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (arr[j] < arr[i]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } maxLength = Math.max(maxLength, dp[i]); } return maxLength; } public static void main(String[] args) { int[] arr = {10, 22, 9, 33, 21, 50, 41, 60}; System.out.println("Array: " + Arrays.toString(arr)); System.out.println("LIS length: " + lis(arr)); // LIS: {10, 22, 33, 50, 60} → length 5 } }

Output

Array: [10, 22, 9, 33, 21, 50, 41, 60]
LIS length: 5

Time: O(n²), Space: O(n) (Can be optimized to O(n log n) with binary search)

Edit Distance (Levenshtein Distance)

Problem: Find minimum operations (insert, delete, replace) to convert one string to another.

Example

public class EditDistance { public static int editDistance(String s1, String s2) { int m = s1.length(), n = s2.length(); int[][] dp = new int[m + 1][n + 1]; // Base cases for (int i = 0; i <= m; i++) dp[i][0] = i; // Delete all chars from s1 for (int j = 0; j <= n; j++) dp[0][j] = j; // Insert all chars of s2 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s1.charAt(i-1) == s2.charAt(j-1)) { dp[i][j] = dp[i-1][j-1]; // No operation needed } else { dp[i][j] = 1 + Math.min(dp[i-1][j-1], // Replace Math.min(dp[i-1][j], // Delete dp[i][j-1])); // Insert } } } return dp[m][n]; } public static void main(String[] args) { String[][] pairs = {{"kitten", "sitting"}, {"sunday", "saturday"}, {"abc", "abc"}}; for (String[] pair : pairs) { System.out.println(pair[0] + " → " + pair[1] + " : " + editDistance(pair[0], pair[1]) + " operations"); } } }

Output

kitten → sitting : 3 operations
sunday → saturday : 3 operations
abc → abc : 0 operations

Subset Sum Problem

Problem: Given a set of positive integers, determine if there is a subset that sums to a target.

Example

public class SubsetSum { public static boolean hasSubsetSum(int[] nums, int target) { int n = nums.length; boolean[][] dp = new boolean[n + 1][target + 1]; // Base case: sum 0 is always achievable (empty subset) for (int i = 0; i <= n; i++) dp[i][0] = true; for (int i = 1; i <= n; i++) { for (int s = 1; s <= target; s++) { dp[i][s] = dp[i-1][s]; // Exclude current element if (nums[i-1] <= s) { dp[i][s] = dp[i][s] || dp[i-1][s - nums[i-1]]; // Include } } } return dp[n][target]; } public static void main(String[] args) { int[] nums = {3, 34, 4, 12, 5, 2}; int[] targets = {9, 30, 11, 7}; System.out.println("Set: " + java.util.Arrays.toString(nums)); for (int target : targets) { System.out.println("Target " + target + ": " + hasSubsetSum(nums, target)); } } }

Output

Set: [3, 34, 4, 12, 5, 2]
Target 9: true
Target 30: false
Target 11: true
Target 7: true

DP Problem-Solving Framework

Step-by-Step Approach

Identify if it's a DP problem:

Can you solve it recursively?
Are there overlapping subproblems?
Does optimal substructure exist?

Define the state:

What parameters uniquely identify a subproblem?
Example: dp[i] = answer for first i elements

Write the recurrence relation:

How does dp[i] depend on smaller subproblems?
Example: dp[i] = dp[i-1] + dp[i-2]

Identify base cases:

What are the trivial subproblems you can solve directly?

Choose approach:

Top-down (memoization) or Bottom-up (tabulation)

Optimize space if possible (use only previous row/values)

Common Mistakes

Incorrect base cases — forgetting to handle edge cases (n=0, empty arrays)
Wrong recurrence relation — not considering all possible transitions
Off-by-one indexing — confusion between 0-indexed and 1-indexed
Not recognizing DP — solving with brute force when DP applies
Integer overflow — large DP values exceeding int range
Insufficient memo/table size — allocating array too small
Not optimizing space — using 2D table when 1D suffices

Best Practices

Start with recursion — understand the problem recursively first
Draw the recursion tree — identify overlapping subproblems visually
Use meaningful state names — dp[i][j] with clear comments
Test with small inputs — verify by hand for n=3,4,5
Print the DP table for debugging
Optimize space after correctness is verified
Consider constraints — if n ≤ 10^3, O(n²) is fine; if n ≤ 10^5, need O(n log n)
Learn common patterns — knapsack, LCS, LIS, grid paths, intervals

Interview Questions

Q1: What is Dynamic Programming? An algorithmic technique that solves problems by breaking them into overlapping subproblems, solving each once, and storing results to avoid recomputation.

Q2: What are the two approaches to DP? Top-down (memoization with recursion) and Bottom-up (tabulation with iteration).

Q3: When should you use DP? When a problem has overlapping subproblems AND optimal substructure — usually optimization or counting problems.

Q4: What is memoization? Storing results of expensive function calls and returning the cached result when the same inputs occur again.

Q5: Memoization vs Tabulation? Memoization: recursive, top-down, solves only needed subproblems. Tabulation: iterative, bottom-up, solves all subproblems, no recursion stack.

Q6: Time complexity of 0/1 Knapsack? O(n × W) where n is number of items and W is knapsack capacity. This is pseudo-polynomial.

Q7: How to identify if a problem is DP? Look for: "find minimum/maximum", "count number of ways", "is it possible", overlapping recursive calls, and optimal substructure.

Q8: What is the difference between DP and Greedy? DP explores all possibilities and guarantees optimal. Greedy makes locally optimal choices and doesn't always give global optimal.

Q9: How to reconstruct the solution (not just the value)? Backtrack through the DP table: at each cell, determine which choice was made (include/exclude) and trace the path.

Q10: Can DP solve problems with exponential state space? Only if the number of unique states is polynomial. If states are truly exponential, DP doesn't help.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Dynamic Programming in Java.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Java Master Course topic.

Search Terms

java-master-course, java master course, java, master, course, dsa, dynamic, programming

Continue learning this concept

DSA in JavaGraph Data Structure in JavaComplete guide to graphs — representation, BFS, DFS, shortest path algorithms, topological sort, and classic graph problems in Java.DSA in JavaHashing in JavaComplete guide to hashing — hash functions, collision resolution, HashMap internals, custom hashCode/equals, and applications of hashing in problem-solving.DSA in JavaHeap (DSA)Complete guide to Heap data structure in Java covering Min Heap, Max Heap, heap operations, heapify algorithm, PriorityQueue class, heap sort, and applications with detailed implementations.DSA in JavaLinked List in JavaComplete guide to Linked Lists — Singly, Doubly, and Circular linked lists with Java implementations, operations, and classic interview problems.DSA in JavaQueue in JavaComplete guide to Queue data structure — FIFO principle, circular queue, priority queue, deque, BFS applications, and classic problems.DSA in JavaRecursion in JavaMaster recursion — base cases, recursive thinking, call stack visualization, tail recursion, memoization, backtracking, and converting recursion to iteration.

PreviousSpring Framework Introduction NextGraph Data Structure in Java

Java Notes

Dynamic Programming in Java

Complete guide to Dynamic Programming in Java covering memoization, tabulation, classical DP problems (Fibonacci, Knapsack, LCS, LIS, Coin Change), time/space optimization, and interview patterns.

What is Dynamic Programming?

The Two Key Properties

For a problem to be solvable with DP, it must have:

1. Overlapping Subproblems: The same subproblems are solved multiple times during recursion. DP stores (caches) these results to avoid redundant computation.

2. Optimal Substructure: The optimal solution to the problem can be constructed from optimal solutions of its subproblems.

Analogy

Imagine you're asked: "What's 1+1+1+1+1+1+1+1+1+1?"

You count: "10." Now someone adds "+1" to the end. You don't recount from scratch — you remember the previous answer (10) and add 1 → 11.

That's Dynamic Programming: remembering past results to avoid recomputation.

Two Approaches to DP

1. Top-Down (Memoization)

Start with the original problem and recursively break it down
Use a cache (array or HashMap) to store results of subproblems
When a subproblem is encountered again, return the cached result
Natural extension of recursive thinking

2. Bottom-Up (Tabulation)

Start with the smallest subproblems and build up to the solution
Use a table (array) to store results iteratively
No recursion — avoids stack overflow
Usually more space-efficient (can sometimes reduce dimensions)

Fibonacci — The Classic DP Example

Pure Recursion (Exponential — BAD)

java example

public class FibonacciRecursive {
    static int fib(int n) {
        if (n <= 1) return n;
        return fib(n - 1) + fib(n - 2); // Recomputes same values!
    }
    
    public static void main(String[] args) {
        System.out.println("fib(10) = " + fib(10));
        System.out.println("fib(20) = " + fib(20));
        // fib(50) would take MINUTES — exponential time!
    }
}

Output

fib(10) = 55
fib(20) = 6765

Problem: fib(5) computes fib(3) twice, fib(2) three times, etc. Time: O(2^n).

Recursion Tree for fib(5):

Example

fib(5) / \ fib(4) fib(3) ← fib(3) computed TWICE / \ / \ fib(3) fib(2) fib(2) fib(1) ← fib(2) computed THREE times / \ / \ / \ fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) / \ fib(1) fib(0)

Top-Down with Memoization (O(n))

Example

Output

fib(40) = 102334155
First 15: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

Time: O(n) — each subproblem computed once. Space: O(n) — memo array + recursion stack.

Bottom-Up Tabulation (O(n) time, O(n) space)

Example

Output

fib(10) = 55
fib(40) = 102334155
fib(50) = 1264937032

Space-Optimized (O(1) space)

Since each Fibonacci value only depends on the previous two, we don't need the entire array:

Example

Output

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

Time: O(n), Space: O(1) — optimal!

Climbing Stairs Problem

Problem: You can climb 1 or 2 stairs at a time. How many distinct ways to reach step n?

Example

Output

Steps 1: 1 ways
Steps 2: 2 ways
Steps 3: 3 ways
Steps 4: 5 ways
Steps 5: 8 ways
Steps 6: 13 ways
Steps 7: 21 ways
Steps 8: 34 ways
Steps 9: 55 ways
Steps 10: 89 ways

Dry Run for n=4:

Example

dp[1] = 1 (just take 1 step) dp[2] = 2 (1+1 or 2) dp[3] = dp[2] + dp[1] = 2 + 1 = 3 (1+1+1, 1+2, 2+1) dp[4] = dp[3] + dp[2] = 3 + 2 = 5 (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)

0/1 Knapsack Problem

Problem: Given n items with weights and values, and a knapsack capacity W, find the maximum value you can carry without exceeding the weight limit. Each item can be included at most once.

Example

Output

Items:
  Item 1: weight=2, value=3
  Item 2: weight=3, value=4
  Item 3: weight=4, value=5
  Item 4: weight=5, value=6
Maximum value: 10

Time: O(n × W), Space: O(n × W)

Dry Run (partial DP table):

i=0	0 0 0 0 0 0 0 0 0
i=1	0 0 3 3 3 3 3 3 3
i=2	0 0 3 4 4 7 7 7 7
i=3	0 0 3 4 5 7 8 9 9
i=4	0 0 3 4 5 7 8 9 10

Longest Common Subsequence (LCS)

Problem: Find the length of the longest subsequence common to two strings.

Example

Output

String 1: ABCBDAB
String 2: BDCAB
LCS length: 4

Time: O(m × n), Space: O(m × n)

Coin Change Problem

Problem: Given coins of different denominations and a total amount, find the minimum number of coins needed.

Example

Output

Coins: [1, 5, 10, 25]
Amount 11 → Min coins: 2
Amount 30 → Min coins: 2
Amount 7 → Min coins: 3
Amount 0 → Min coins: 0

Dry Run for amount=11, coins=[1,5,10,25]:

Example

dp[0]=0, dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=4, dp[5]=1 dp[6]=2, dp[7]=3, dp[8]=4, dp[9]=5, dp[10]=1, dp[11]=2 Answer: dp[11] = 2 (one 10 + one 1, or two 5s + one 1)

Longest Increasing Subsequence (LIS)

Example

Output

Array: [10, 22, 9, 33, 21, 50, 41, 60]
LIS length: 5

Time: O(n²), Space: O(n) (Can be optimized to O(n log n) with binary search)

Edit Distance (Levenshtein Distance)

Problem: Find minimum operations (insert, delete, replace) to convert one string to another.

Example

Output

kitten → sitting : 3 operations
sunday → saturday : 3 operations
abc → abc : 0 operations

Subset Sum Problem

Problem: Given a set of positive integers, determine if there is a subset that sums to a target.

Example

Output

Set: [3, 34, 4, 12, 5, 2]
Target 9: true
Target 30: false
Target 11: true
Target 7: true

DP Problem-Solving Framework

Step-by-Step Approach

Identify if it's a DP problem:

Can you solve it recursively?
Are there overlapping subproblems?
Does optimal substructure exist?

Define the state:

What parameters uniquely identify a subproblem?
Example: dp[i] = answer for first i elements

Write the recurrence relation:

How does dp[i] depend on smaller subproblems?
Example: dp[i] = dp[i-1] + dp[i-2]

Identify base cases:

What are the trivial subproblems you can solve directly?

Choose approach:

Top-down (memoization) or Bottom-up (tabulation)

Optimize space if possible (use only previous row/values)

Common Mistakes

Incorrect base cases — forgetting to handle edge cases (n=0, empty arrays)
Wrong recurrence relation — not considering all possible transitions
Off-by-one indexing — confusion between 0-indexed and 1-indexed
Not recognizing DP — solving with brute force when DP applies
Integer overflow — large DP values exceeding int range
Insufficient memo/table size — allocating array too small
Not optimizing space — using 2D table when 1D suffices

Best Practices

Start with recursion — understand the problem recursively first
Draw the recursion tree — identify overlapping subproblems visually
Use meaningful state names — dp[i][j] with clear comments
Test with small inputs — verify by hand for n=3,4,5
Print the DP table for debugging
Optimize space after correctness is verified
Consider constraints — if n ≤ 10^3, O(n²) is fine; if n ≤ 10^5, need O(n log n)
Learn common patterns — knapsack, LCS, LIS, grid paths, intervals