Module 12 :Dynamic Programming

Dynamic Programming (DP) is not about memorizing problems.
It is about recognizing repeated work and optimizing decisions.

At its core, DP answers one question:

“Can I break this problem into smaller overlapping subproblems and reuse their answers?”

---

DP Concepts & States

What is a DP State?

A state represents the minimum information needed to make future decisions.

Example:

• Fibonacci → dp[n]
• Grid paths → dp[i][j]
• Knapsack → dp[index][weight]

Good DP states are:

• Minimal
• Meaningful
• Reusable

Bad state design = impossible DP.

---

Memoization vs Tabulation

Memoization (Top-Down)

• Recursive
• Cache results
• Natural thinking
• Slower due to recursion overhead

int fib(int n){
    if(n <= 1) return n;
    if(dp[n] != -1) return dp[n];
    return dp[n] = fib(n-1) + fib(n-2);
}

---

Tabulation (Bottom-Up)

• Iterative
• Faster
• More space-optimized
• Preferred in interviews

dp[0] = 0;
dp[1] = 1;

for(int i = 2; i <= n; i++)
    dp[i] = dp[i-1] + dp[i-2];

---

1D DP Problems

Pattern

Each state depends on previous one or two states.

---

Example: Climbing Stairs

You can climb 1 or 2 steps.

dp[0] = 1;
dp[1] = 1;

for(int i = 2; i <= n; i++)
    dp[i] = dp[i-1] + dp[i-2];

Time: O(n)
Space can be optimized to O(1).

---

2D DP Problems

Pattern

Two changing variables (index + capacity, string lengths, grid).

---

Example: Unique Paths in Grid

for(int i = 0; i < m; i++)
    dp[i][0] = 1;

for(int j = 0; j < n; j++)
    dp[0][j] = 1;

for(int i = 1; i < m; i++)
    for(int j = 1; j < n; j++)
        dp[i][j] = dp[i-1][j] + dp[i][j-1];

---

Subset Sum

Problem

Is there a subset with sum = target?

---

DP Definition

dp[i][s] → can we form sum s using first i elements?

---

dp[0][0] = true;

for(int i = 1; i <= n; i++){
    for(int s = 0; s <= sum; s++){
        dp[i][s] = dp[i-1][s];
        if(s >= arr[i-1])
            dp[i][s] |= dp[i-1][s - arr[i-1]];
    }
}

This is the foundation of knapsack problems.

---

Knapsack Problems

0/1 Knapsack

Each item can be chosen once.

dp[i][w] = max(
    dp[i-1][w],
    value[i] + dp[i-1][w - weight[i]]
)

---

Unbounded Knapsack

Items can be chosen multiple times.

Key difference:

dp[i][w] = max(
    dp[i-1][w],
    value[i] + dp[i][w - weight[i]]
)

Used in:

• Rod cutting
• Coin change (max ways)

---

Coin Change

Minimum Coins Problem

dp[0] = 0;

for(int i = 1; i <= amount; i++){
    dp[i] = INF;
    for(int coin : coins){
        if(i >= coin)
            dp[i] = Math.min(dp[i], dp[i - coin] + 1);
    }
}

---

Number of Ways

dp[0] = 1;

for(int coin : coins){
    for(int i = coin; i <= amount; i++)
        dp[i] += dp[i - coin];
}

---

Longest Common Subsequence (LCS)

Problem

Find longest sequence common to both strings.

---

for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
        if(s1.charAt(i-1) == s2.charAt(j-1))
            dp[i][j] = 1 + dp[i-1][j-1];
        else
            dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
    }
}

Used in:

• Diff tools
• DNA matching
• Text comparison

---

Longest Increasing Subsequence (LIS)

O(n²) DP Approach

for(int i = 0; i < n; i++){
    dp[i] = 1;
    for(int j = 0; j < i; j++){
        if(arr[j] < arr[i])
            dp[i] = Math.max(dp[i], dp[j] + 1);
    }
}

---

Optimized O(n log n) (Conceptual)

Uses binary search + patience sorting idea.

---

Matrix Chain Multiplication

Problem

Find minimum cost to multiply matrices.

---

DP Definition

dp[i][j] → minimum cost to multiply matrices i to j

for(int len = 2; len <= n; len++){
    for(int i = 1; i + len - 1 <= n; i++){
        int j = i + len - 1;
        dp[i][j] = INF;

        for(int k = i; k < j; k++){
            dp[i][j] = Math.min(
                dp[i][j],
                dp[i][k] + dp[k+1][j] + arr[i-1]*arr[k]*arr[j]
            );
        }
    }
}

Classic partition DP.

---

DP on Trees

Pattern

Use postorder traversal.

---

Example: Maximum Path Sum

int maxPath(TreeNode root){
    if(root == null) return 0;
    int left = Math.max(0, maxPath(root.left));
    int right = Math.max(0, maxPath(root.right));
    globalMax = Math.max(globalMax, root.val + left + right);
    return root.val + Math.max(left, right);
}

Tree DP often returns values to parent.

---

DP on Grids

Example: Minimum Path Sum

dp[0][0] = grid[0][0];

for(int i = 1; i < m; i++)
    dp[i][0] = dp[i-1][0] + grid[i][0];

for(int j = 1; j < n; j++)
    dp[0][j] = dp[0][j-1] + grid[0][j];

for(int i = 1; i < m; i++)
    for(int j = 1; j < n; j++)
        dp[i][j] = grid[i][j] + 
                   Math.min(dp[i-1][j], dp[i][j-1]);

---

Bitmask DP (Introduction)

Used when:

• n ≤ 20
• Subsets matter
• Exponential states acceptable

---

Example: Traveling Salesman (Concept)

State:

dp[mask][i]

Meaning:
Minimum cost to visit cities in mask ending at city i.

---

dp[mask | (1 << j)][j] = min(
    dp[mask | (1 << j)][j],
    dp[mask][i] + cost[i][j]
);

Very powerful but advanced.