Unit 5: Dynamic Programming Problems

Opening Hook — DP Powers the Products You Use Daily

Learning Outcomes — Bloom's Taxonomy Mapped (12 Outcomes)

Concept Explanation — 7 Classic DP Problems

Each problem follows the standard DP methodology: Problem Statement → Intuition → Recurrence → DP Table Trace → Code (C++/Python) → Complexity → Optimization. Master this framework and you can solve any new DP problem.

1. Binomial Coefficient C(n, k)

Intuition — Pascal's Triangle

Every entry in Pascal's triangle is the sum of the two entries directly above it. The value at row n, position k is exactly C(n, k). Instead of computing factorials (which overflow for large n), we build the triangle row by row.

Recurrence Relation

Recurrence
// Pascal's Rule:
C(n, k) = C(n-1, k-1) + C(n-1, k)

// Base cases:
C(n, 0) = 1        // choosing 0 items = 1 way (empty set)
C(n, n) = 1        // choosing all items = 1 way

DP Table Trace — C(5, 2)

Answer: C(5, 2) = 10 ✅

Code — C++

C++
int binomialCoeff(int n, int k) {
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;  // C(i, 0) = 1
        for (int j = 1; j <= min(i, k); j++) {
            if (j == i)
                dp[i][j] = 1;  // C(i, i) = 1
            else
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
        }
    }
    return dp[n][k];
}

Code — Python

Python
def binomial_coeff(n, k):
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 1
        for j in range(1, min(i, k) + 1):
            if j == i:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
    return dp[n][k]

print(binomial_coeff(5, 2))  # Output: 10

Complexity

Space Optimization — O(k)

C++
int binomialOptimized(int n, int k) {
    vector<int> dp(k + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = min(i, k); j > 0; j--)  // right to left!
            dp[j] = dp[j] + dp[j - 1];
    return dp[k];
}

2. Box Stacking Problem

Intuition — Reduce to LIS Variant

For each box, generate all 3 rotations (each face as base). Sort all rotations by base area (decreasing). Now the problem becomes: find the longest increasing subsequence of heights where each box's base dimensions are strictly smaller than the one below it — a variant of LIS!

Algorithm Steps

1. Generate rotations: For box (h, w, d), create 3 rotations where each dimension is the height and the base is (max of remaining, min of remaining)
2. Sort by base area in decreasing order
3. Apply LIS-like DP: dp[i] = max stack height with box i on top

Recurrence

Recurrence
// For each box i (sorted by base area descending):
dp[i] = height[i]   // base case: just box i alone

// For all j < i where box j's base fits strictly inside box i's base:
dp[i] = max(dp[i], dp[j] + height[i])
    where width[j] < width[i] AND depth[j] < depth[i]

Answer = max(dp[0], dp[1], ..., dp[n-1])

Trace Example

Given boxes: (4,6,7), (1,2,3), (4,5,6)

All rotations (h, w, d where w ≥ d):

After sorting by base area (descending) and running DP: Maximum height = 22

Code — C++

C++
#include <bits/stdc++.h>
using namespace std;

struct Box { int h, w, d; };

bool cmp(Box &a, Box &b) {
    return (a.w * a.d) > (b.w * b.d);
}

int maxStackHeight(int height[], int width[], int depth[], int n) {
    vector<Box> rot;
    for (int i = 0; i < n; i++) {
        int dims[] = {height[i], width[i], depth[i]};
        sort(dims, dims+3);
        // 3 rotations: each dimension as height
        rot.push_back({dims[0], max(dims[1],dims[2]), min(dims[1],dims[2])});
        rot.push_back({dims[1], max(dims[0],dims[2]), min(dims[0],dims[2])});
        rot.push_back({dims[2], max(dims[0],dims[1]), min(dims[0],dims[1])});
    }
    sort(rot.begin(), rot.end(), cmp);

    int m = rot.size();
    vector<int> dp(m);
    for (int i = 0; i < m; i++) dp[i] = rot[i].h;

    for (int i = 1; i < m; i++)
        for (int j = 0; j < i; j++)
            if (rot[i].w < rot[j].w && rot[i].d < rot[j].d)
                dp[i] = max(dp[i], dp[j] + rot[i].h);

    return *max_element(dp.begin(), dp.end());
}

Code — Python

Python
def max_stack_height(boxes):
    rotations = []
    for h, w, d in boxes:
        dims = sorted([h, w, d])
        rotations.append((dims[0], max(dims[1],dims[2]), min(dims[1],dims[2])))
        rotations.append((dims[1], max(dims[0],dims[2]), min(dims[0],dims[2])))
        rotations.append((dims[2], max(dims[0],dims[1]), min(dims[0],dims[1])))

    rotations.sort(key=lambda x: x[1] * x[2], reverse=True)
    n = len(rotations)
    dp = [r[0] for r in rotations]

    for i in range(1, n):
        for j in range(i):
            if rotations[i][1] < rotations[j][1] and \
               rotations[i][2] < rotations[j][2]:
                dp[i] = max(dp[i], dp[j] + rotations[i][0])

    return max(dp)

print(max_stack_height([(4,6,7), (1,2,3), (4,5,6)]))  # Output: 22

Complexity

3. Integer Knapsack (0/1, Duplicate Items Forbidden)

Recurrence Relation

Recurrence
dp[i][w] = maximum value using first i items with capacity w

// Choice: include item i or exclude it
dp[i][w] = max(
    dp[i-1][w],                      // don't take item i
    dp[i-1][w - wt[i]] + val[i]      // take item i (if wt[i] ≤ w)
)

// Base cases:
dp[0][w] = 0   // 0 items → 0 value
dp[i][0] = 0   // 0 capacity → 0 value

Full DP Table Trace — 4 Items, W = 7

Items: (1,1), (3,4), (4,5), (5,7) — (weight, value)

Answer: dp[4][7] = 9 (take items 2 and 3: weight 3+4=7, value 4+5=9) ✅

Trace Walkthrough

Reading dp[4][7]=9: Can we include item 4 (wt=5, val=7)? dp[3][7-5]+7 = dp[3][2]+7 = 1+7 = 8. Don't include: dp[3][7]=9. So 9 > 8 → don't take item 4. Move to dp[3][7]=9. Include item 3 (wt=4, val=5)? dp[2][7-4]+5 = dp[2][3]+5 = 4+5 = 9 ✅. Take item 3. Move to dp[2][3]=4. Include item 2 (wt=3, val=4)? dp[1][0]+4 = 0+4 = 4 ✅. Take item 2. Done → Items {2, 3}.

Code — C++

C++
int knapsack(int W, int wt[], int val[], int n) {
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i-1][w];  // don't take item i
            if (wt[i-1] <= w)
                dp[i][w] = max(dp[i][w], dp[i-1][w - wt[i-1]] + val[i-1]);
        }
    }
    return dp[n][W];
}

Code — Python

Python
def knapsack(W, wt, val, n):
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(W + 1):
            dp[i][w] = dp[i-1][w]
            if wt[i-1] <= w:
                dp[i][w] = max(dp[i][w], dp[i-1][w - wt[i-1]] + val[i-1])
    return dp[n][W]

print(knapsack(7, [1,3,4,5], [1,4,5,7], 4))  # Output: 9

Space Optimization — 1D Array

C++
int knapsack1D(int W, int wt[], int val[], int n) {
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; i++)
        for (int w = W; w >= wt[i]; w--)  // RIGHT TO LEFT!
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
    return dp[W];
}

Complexity

4. Edit Distance (Levenshtein Distance)

Recurrence Relation

Recurrence
dp[i][j] = min edits to convert A[0..i-1] to B[0..j-1]

if A[i-1] == B[j-1]:
    dp[i][j] = dp[i-1][j-1]           // characters match, no operation
else:
    dp[i][j] = 1 + min(
        dp[i-1][j],      // DELETE from A
        dp[i][j-1],      // INSERT into A
        dp[i-1][j-1]     // REPLACE in A
    )

// Base cases:
dp[i][0] = i    // delete all i chars from A
dp[0][j] = j    // insert all j chars into empty A

Full DP Table Trace — "saturday" → "sunday"

Answer: Edit Distance = 3 (delete 'a', delete 't', replace 'r'→'n') ✅

Code — C++

C++
int editDistance(string A, string B) {
    int m = A.size(), n = B.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (A[i-1] == B[j-1])
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
        }
    }
    return dp[m][n];
}

Code — Python

Python
def edit_distance(A, B):
    m, n = len(A), len(B)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): dp[i][0] = i
    for j in range(n + 1): dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i-1] == B[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

print(edit_distance("saturday", "sunday"))  # Output: 3

Complexity

5. Longest Increasing Subsequence (LIS)

Approach 1: O(n²) DP

Recurrence

Recurrence
dp[i] = length of LIS ending at index i

dp[i] = 1 + max(dp[j]) for all j < i where arr[j] < arr[i]

// Base case:
dp[i] = 1 for all i  // every element is an LIS of length 1

Answer = max(dp[0], dp[1], ..., dp[n-1])

DP Table Trace

Array: [10, 22, 9, 33, 21, 50, 41, 60, 80]

Trace for dp[5]=4: arr[5]=50. Check j=0: 10<50 → dp[0]+1=2. j=1: 22<50 → dp[1]+1=3. j=2: 9<50 → 2. j=3: 33<50 → dp[3]+1=4. j=4: 21<50 → 3. Best = 4.

Answer: max(dp) = 6 ✅

Code — O(n²) C++

C++
int lis_n2(int arr[], int n) {
    vector<int> dp(n, 1);
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if (arr[j] < arr[i])
                dp[i] = max(dp[i], dp[j] + 1);
    return *max_element(dp.begin(), dp.end());
}

Approach 2: O(n log n) — Patience Sorting with Binary Search

Intuition: Maintain an array tails[] where tails[i] = smallest tail element of all increasing subsequences of length i+1. For each new element, use binary search to find its position.

Code — O(n log n) C++

C++
int lis_nlogn(int arr[], int n) {
    vector<int> tails;
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(tails.begin(), tails.end(), arr[i]);
        if (it == tails.end())
            tails.push_back(arr[i]);  // extend longest subsequence
        else
            *it = arr[i];             // replace to keep smallest tail
    }
    return tails.size();
}

Code — O(n log n) Python

Python
from bisect import bisect_left

def lis_nlogn(arr):
    tails = []
    for x in arr:
        pos = bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)

print(lis_nlogn([10,22,9,33,21,50,41,60,80]))  # Output: 6

Complexity Comparison

6. Longest Common Subsequence (LCS)

Recurrence Relation

Recurrence
dp[i][j] = LCS of X[0..i-1] and Y[0..j-1]

if X[i-1] == Y[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1       // characters match
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])  // skip one char from either

// Base cases:
dp[0][j] = 0    // empty X
dp[i][0] = 0    // empty Y

Full DP Table Trace — "ABCBDAB" and "BDCAB"

Answer: LCS length = 4 ✅

Backtracking to Find Actual Subsequence

Start at dp[7][5]=4. X[6]='B'==Y[4]='B' → take 'B', go to dp[6][4]. X[5]='A'==Y[3]='A' → take 'A', go to dp[5][3]. X[4]='D'≠Y[2]='C', dp[4][3]>dp[5][2] → go left dp[5][2]. X[4]='D'==Y[1]='D' → wait, we're at (5,2). X[4]='D'==Y[1]='D' → take 'D', go to dp[4][1]. dp[3][1]=1, X[2]='C'≠Y[0]='B', go up. dp[2][1]=1, X[1]='B'==Y[0]='B' → take 'B', go to dp[1][0]=0. Done.

LCS (reversed): B, D, A, B → "BDAB" (one of the valid LCS; "BCAB" is another)

Code — C++

C++
int lcs(string X, string Y) {
    int m = X.size(), n = Y.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (X[i-1] == Y[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];
}

// Backtrack to find actual LCS:
string findLCS(string X, string Y, vector<vector<int>>& dp) {
    string result = "";
    int i = X.size(), j = Y.size();
    while (i > 0 && j > 0) {
        if (X[i-1] == Y[j-1]) {
            result = X[i-1] + result;
            i--; j--;
        } else if (dp[i-1][j] > dp[i][j-1])
            i--;
        else
            j--;
    }
    return result;
}

Code — Python

Python
def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[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]

print(lcs("ABCBDAB", "BDCAB"))  # Output: 4

Complexity

7. Balanced Partition Problem

Reduction to Subset Sum

If total sum = S, we want to find a subset with sum as close to S/2 as possible. If we find the largest achievable sum ≤ S/2, call it maxSum, then minimum difference = S − 2 × maxSum. This reduces to the Subset Sum problem.

Recurrence

Recurrence
dp[i][j] = true if a subset of first i elements can sum to j

dp[i][j] = dp[i-1][j]              // don't include arr[i-1]
         OR dp[i-1][j - arr[i-1]]  // include arr[i-1]

// Base cases:
dp[i][0] = true   // empty subset sums to 0
dp[0][j] = false  // no elements, can't make non-zero sum

Answer: Find largest j ≤ S/2 where dp[n][j] == true
        Min difference = S - 2*j

Code — C++

C++
int balancedPartition(int arr[], int n) {
    int S = 0;
    for (int i = 0; i < n; i++) S += arr[i];

    vector<vector<bool>> dp(n + 1, vector<bool>(S / 2 + 1, false));
    for (int i = 0; i <= n; i++) dp[i][0] = true;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= S / 2; j++) {
            dp[i][j] = dp[i-1][j];
            if (arr[i-1] <= j)
                dp[i][j] = dp[i][j] || dp[i-1][j - arr[i-1]];
        }

    for (int j = S / 2; j >= 0; j--)
        if (dp[n][j]) return S - 2 * j;
    return S;
}

Code — Python

Python
def balanced_partition(arr):
    S = sum(arr)
    n = len(arr)
    half = S // 2
    dp = [[False] * (half + 1) for _ in range(n + 1)]
    for i in range(n + 1): dp[i][0] = True

    for i in range(1, n + 1):
        for j in range(1, half + 1):
            dp[i][j] = dp[i-1][j]
            if arr[i-1] <= j:
                dp[i][j] = dp[i][j] or dp[i-1][j - arr[i-1]]

    for j in range(half, -1, -1):
        if dp[n][j]:
            return S - 2 * j

print(balanced_partition([1, 6, 11, 5]))  # Output: 1

Complexity

Learn by Doing — 3-Tier Lab Structure

Python
def lis(arr):
    n = len(arr)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

print(lis([3, 10, 2, 1, 20]))  # Output: 3

Problem Set — Tracing, Programming & Interview Problems

Part 1: DP Table Tracing (5 Problems)

T1. Fill the complete DP table for LCS of X="AGGTAB" and Y="GXTXAYB". What is the LCS length?

T2. Trace the 0/1 Knapsack DP table for items [(1,1), (2,6), (3,10), (5,15), (7,16)] with W=8. Which items are selected?

T3. Fill the Edit Distance DP table for "kitten" → "sitting". Show all 7×8 = 56 cells.

T4. Trace the LIS dp[] array for [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]. What is the LIS length?

T5. Fill the Binomial Coefficient table (Pascal's Triangle) for n=8, and find C(8,3) and C(8,5). Verify C(8,3) = C(8,5).

Part 2: Programming Problems (8 Problems)

P1. Beginner Implement LIS with O(n²) DP. Input: array of integers. Output: LIS length.

P2. Beginner Implement LCS for two strings. Print both the length and the actual subsequence.

P3. Intermediate Implement 0/1 Knapsack with backtracking to print selected items.

P4. Intermediate Implement Edit Distance and print the sequence of operations to transform A to B.

P5. Intermediate Implement Box Stacking. Handle all 3 rotations correctly. Print the stack order.

P6. Intermediate Implement Balanced Partition and print both subsets.

P7. Advanced Implement LIS in O(n log n) using binary search. Reconstruct the actual subsequence (not just length).

P8. Advanced Given a grid of m×n with positive integers, find the path from top-left to bottom-right with minimum sum (move only right or down). Use DP.

Part 3: Industry Application Problems (3 Problems)

Part 4: Interview Questions (3 Problems)

MCQ Assessment Bank — 30 Questions (Bloom's Mapped)

Remember / Identify (Q1–Q5)

Understand / Explain (Q6–Q10)

Apply / Compute (Q11–Q15)

Analyze / Compare (Q16–Q20)

Evaluate / Judge (Q21–Q25)

Create / Design (Q26–Q30)

Short Answer Questions (8 Questions)

Long Answer Questions (3 Questions)

C++
int knapsack(int W, int wt[], int val[], int n) {
    int dp[n+1][W+1];
    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=n; i++)
        for(int w=1; w<=W; w++) {
            dp[i][w] = dp[i-1][w];
            if(wt[i-1] <= w)
                dp[i][w] = max(dp[i][w],
                    dp[i-1][w-wt[i-1]] + val[i-1]);
        }
    return dp[n][W];
}

Lab Programs — Complete Code, Output & Viva Questions

C++
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cout << "Enter array size: ";
    cin >> n;
    vector<int> arr(n), dp(n, 1);
    cout << "Enter elements: ";
    for (int i = 0; i < n; i++) cin >> arr[i];

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

    cout << "LIS Length: " << *max_element(dp.begin(), dp.end());
    return 0;
}

C++
#include <bits/stdc++.h>
using namespace std;

int main() {
    string X, Y;
    cout << "Enter string X: "; cin >> X;
    cout << "Enter string Y: "; cin >> Y;
    int m = X.size(), n = Y.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (X[i-1] == Y[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

    // Backtrack to find LCS string
    string lcs = "";
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (X[i-1] == Y[j-1]) { lcs = X[i-1] + lcs; i--; j--; }
        else if (dp[i-1][j] > dp[i][j-1]) i--;
        else j--;
    }

    cout << "LCS Length: " << dp[m][n] << endl;
    cout << "LCS: " << lcs << endl;
    return 0;
}

Python
def binomial(n, k):
    dp = [0] * (k + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        for j in range(min(i, k), 0, -1):
            dp[j] = dp[j] + dp[j - 1]
    return dp[k]

n, k = map(int, input("Enter n and k: ").split())
print(f"C({n},{k}) = {binomial(n, k)}")

Python
def max_stack_height(boxes):
    rot = []
    for h, w, d in boxes:
        dims = sorted([h, w, d])
        # Generate all 3 rotations
        rot.append((dims[0], max(dims[1],dims[2]), min(dims[1],dims[2])))
        rot.append((dims[1], max(dims[0],dims[2]), min(dims[0],dims[2])))
        rot.append((dims[2], max(dims[0],dims[1]), min(dims[0],dims[1])))

    rot.sort(key=lambda x: x[1]*x[2], reverse=True)
    n = len(rot)
    dp = [r[0] for r in rot]

    for i in range(1, n):
        for j in range(i):
            if rot[i][1] < rot[j][1] and rot[i][2] < rot[j][2]:
                dp[i] = max(dp[i], dp[j] + rot[i][0])

    return max(dp)

boxes = [(4,6,7), (1,2,3), (4,5,6)]
print(f"Max stack height: {max_stack_height(boxes)}")

C++
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, W;
    cout << "Enter number of items and capacity: ";
    cin >> n >> W;
    vector<int> wt(n), val(n);
    cout << "Enter weight and value for each item:\n";
    for (int i = 0; i < n; i++) cin >> wt[i] >> val[i];

    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
    for (int i = 1; i <= n; i++)
        for (int w = 1; w <= W; w++) {
            dp[i][w] = dp[i-1][w];
            if (wt[i-1] <= w)
                dp[i][w] = max(dp[i][w], dp[i-1][w-wt[i-1]] + val[i-1]);
        }

    cout << "Maximum value: " << dp[n][W] << endl;

    // Backtrack to find selected items
    cout << "Selected items: ";
    int w = W;
    for (int i = n; i > 0; i--)
        if (dp[i][w] != dp[i-1][w]) {
            cout << i << " ";
            w -= wt[i-1];
        }
    return 0;
}

Python
def edit_distance(A, B):
    m, n = len(A), len(B)
    dp = [[0]*(n+1) for _ in range(m+1)]

    for i in range(m+1): dp[i][0] = i
    for j in range(n+1): dp[0][j] = j

    for i in range(1, m+1):
        for j in range(1, n+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j],
                                   dp[i][j-1],
                                   dp[i-1][j-1])
    return dp[m][n]

A = input("Enter string A: ")
B = input("Enter string B: ")
print(f"Edit Distance: {edit_distance(A, B)}")

C++
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cout << "Enter array size: ";
    cin >> n;
    vector<int> arr(n);
    cout << "Enter elements: ";
    int S = 0;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        S += arr[i];
    }

    int half = S / 2;
    vector<bool> dp(half + 1, false);
    dp[0] = true;

    for (int i = 0; i < n; i++)
        for (int j = half; j >= arr[i]; j--)
            dp[j] = dp[j] || dp[j - arr[i]];

    for (int j = half; j >= 0; j--)
        if (dp[j]) {
            cout << "Minimum difference: " << S - 2 * j << endl;
            break;
        }
    return 0;
}

Industry Spotlight — A Day in the Life

Earn With It — Interview Prep Coaching

How to Start Earning

Step 1: Build Your Proof (2–4 weeks)

• Solve 50+ DP problems on LeetCode/CodeForces
• Get 4-star+ rating on CodeChef or 1600+ on Codeforces
• Create a blog/YouTube channel explaining DP problems

Step 2: Start Coaching (Month 1–2)

• Offer 1-on-1 DP coaching to 3rd/4th year students at ₹500–₹1,000/session
• Create a "DP Masterclass" (7 problems in 7 sessions) for ₹3,000–₹5,000
• Post on LinkedIn: "Cracked FAANG DP problems. DM for coaching."

Step 3: Scale (Month 3+)

• Group sessions (5–10 students): ₹1,000–₹2,000/student for a 10-session course
• Create pre-recorded DP courses on Unacademy/YouTube: passive income
• Conduct mock interviews: ₹500–₹1,500 per session

Chapter Summary — DP Problem Classification

DP Problem Classification Table

The DP Problem-Solving Framework

Connections Between Problems

Earning Checkpoint — Self-Assessment

🎯 Post-Unit Action Items

1. ✅ Solve all 7 problems from memory (no reference)
2. ✅ Complete all 5 tracing exercises (Section E)
3. ✅ Solve at least 5 programming problems from the Problem Set
4. ✅ Score 24/30+ on the MCQ assessment
5. ✅ Solve 20+ DP problems on LeetCode (Easy→Medium)
6. ✅ Create your "DP Masterclass" outline for coaching
7. ✅ Apply to at least 3 companies with DP in their interview process

✅ Unit 5 complete. You now think in states and transitions. Ready for Unit 6!

[QR: Link to EduArtha video tutorial — Dynamic Programming Masterclass]