Unit 4: Basic Dynamic Programming

Opening Hook — The Hidden Algorithm Behind Billions

Learning Outcomes — Bloom's Taxonomy Mapped

Concept Explanation — Dynamic Programming from Scratch

1. Introduction to Dynamic Programming

Dynamic Programming (DP) is an algorithmic technique that solves complex problems by breaking them into simpler overlapping subproblems and storing their solutions to avoid redundant computation. The term was coined by Richard Bellman in the 1950s.

When should you use DP? Two conditions must BOTH hold:

1. Overlapping Subproblems — The same subproblems are solved again and again during recursion.
2. Optimal Substructure — The optimal solution to the problem can be constructed from optimal solutions of its subproblems.

DP = Recursion + Memoization (top-down approach) OR Tabulation (bottom-up approach). Both avoid recomputing the same results.

Naive Recursive Fibonacci (Slow — O(2ⁿ))

C++
// Naive recursive Fibonacci — exponential time!
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}
// fib(5) makes 15 function calls!
// fib(40) makes over 300 million calls!

DP Fibonacci — Tabulation (Fast — O(n))

C++
// DP Fibonacci — linear time, linear space
int fib(int n) {
    if (n <= 1) return n;
    int dp[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];
}
// fib(40) now takes only 40 operations!

2. Tiling Problem

Problem: In how many ways can you fill a 2×n board with 2×1 tiles?

Base cases:

• n = 1: Only 1 way — place one vertical tile. f(1) = 1
• n = 2: Two ways — two vertical tiles OR two horizontal tiles. f(2) = 2

Recurrence: For a 2×n board, either place a vertical tile (leaving a 2×(n-1) board) or place two horizontal tiles (leaving a 2×(n-2) board).

f(n) = f(n−1) + f(n−2)

DP Table Trace for n = 6

Trace: f(3)=f(2)+f(1)=2+1=3, f(4)=f(3)+f(2)=3+2=5, f(5)=f(4)+f(3)=5+3=8, f(6)=f(5)+f(4)=8+5=13.

C++
#include <iostream>
using namespace std;

int tilingWays(int n) {
    if (n <= 2) return n;
    int dp[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

int main() {
    int n;
    cout << "Enter n: ";
    cin >> n;
    cout << "Ways to tile 2x" << n << " board: " << tilingWays(n) << endl;
    return 0;
}

3. Tabulation vs Memoization

Memoization (Top-Down): Start from the original problem, recurse downward, and cache results in a table so each subproblem is solved only once.

Tabulation (Bottom-Up): Start from the smallest subproblems (base cases), and iteratively build up to the final answer using a DP table.

Fibonacci — Memoization (Top-Down)

C++
#include <iostream>
#include <cstring>
using namespace std;

int memo[1001];

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];
}

int main() {
    memset(memo, -1, sizeof(memo));
    cout << fib(6) << endl; // Output: 8
    return 0;
}

Fibonacci — Tabulation (Bottom-Up)

C++
int fib(int n) {
    if (n <= 1) return n;
    int dp[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];
}
// DP Table for fib(6):
// i:     0  1  2  3  4  5  6
// dp[i]: 0  1  1  2  3  5  8

4. Optimal Substructure Property

Definition: A problem has optimal substructure if an optimal solution to the problem contains optimal solutions to its subproblems.

5. Overlapping Subproblems Property

Definition: A problem has overlapping subproblems when the same subproblems are solved again and again during recursion.

Fibonacci Recursion Tree for F(5)

Tree
                        F(5)
                       /    \
                    F(4)     F(3)       ← F(3) computed here
                   /    \    /   \
                F(3)   F(2) F(2) F(1)   ← F(3) also here! F(2) repeated!
               /   \
            F(2)  F(1)                  ← F(2) again!

F(3) is computed 2 times
F(2) is computed 3 times
F(1) is computed 5 times
Total function calls for F(5): 15 calls!

Why naive recursion is O(2ⁿ): The recursion tree is a binary tree. At each level, the number of calls roughly doubles. For F(n), there are approximately 2ⁿ total calls.

Why DP makes it O(n): With memoization or tabulation, each value F(0) through F(n) is computed exactly once and stored. Total work = n computations.

6. Dynamic Programming Process and Techniques

Applying the Framework: Fibonacci

1. State: dp[i] = the i-th Fibonacci number
2. Recurrence: dp[i] = dp[i-1] + dp[i-2]
3. Base cases: dp[0] = 0, dp[1] = 1
4. Iteration order: Left to right (i = 2, 3, …, n)
5. Space optimisation: Only need prev2 and prev1 → O(1) space

Applying the Framework: Climbing Stairs

1. State: dp[i] = number of ways to reach stair i
2. Recurrence: dp[i] = dp[i-1] + dp[i-2] (reach stair i from i-1 by 1 step, or from i-2 by 2 steps)
3. Base cases: dp[0] = 1 (1 way to stay at ground), dp[1] = 1
4. Iteration order: Left to right (i = 2 to n)
5. Space optimisation: Same as Fibonacci → O(1) possible

7. Formulating DP Problems

"Is This a DP Problem?" — Checklist

• ✅ Does the problem ask for optimal (min/max) or count of ways?
• ✅ Can I make a choice at each step (take/skip, include/exclude)?
• ✅ Does the problem have overlapping subproblems?
• ✅ Does it have optimal substructure?
• ✅ Can I define a state that captures the essential information?

If you answer YES to most of these, it's likely a DP problem.

Common DP Patterns

8. Classic DP Examples

8.1 — Climbing Stairs

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

State: dp[i] = number of distinct ways to reach stair i.

Recurrence: dp[i] = dp[i-1] + dp[i-2]

Base cases: dp[0] = 1, dp[1] = 1

DP Table Trace for n = 5

dp[2]=dp[1]+dp[0]=1+1=2. dp[3]=dp[2]+dp[1]=2+1=3. dp[4]=dp[3]+dp[2]=3+2=5. dp[5]=dp[4]+dp[3]=5+3=8.

C++
#include <iostream>
using namespace std;

int climbStairs(int n) {
    if (n <= 1) return 1;
    int dp[n + 1];
    dp[0] = 1; dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

int main() {
    cout << "Ways to climb 5 stairs: " << climbStairs(5) << endl; // Output: 8
    return 0;
}

Time: O(n)   Space: O(n) → can optimise to O(1) using two variables.

8.2 — Coin Change (Minimum Coins)

Problem: Given coins of certain denominations, find the minimum number of coins to make a given amount.

State: dp[i] = minimum coins to make amount i.

Recurrence: dp[i] = min(dp[i - coin] + 1) for all coins where coin ≤ i

Base case: dp[0] = 0 (zero coins for amount 0)

DP Table Trace: amount = 11, coins = {1, 5, 6}

Trace for dp[11]: dp[11] = min(dp[10]+1, dp[6]+1, dp[5]+1) = min(3, 2, 2) = 2. Solution: use coins 5 + 6 = 11.

C++
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i && dp[i - coin] != INT_MAX)
                dp[i] = min(dp[i], dp[i - coin] + 1);
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    vector<int> coins = {1, 5, 6};
    cout << "Min coins for 11: " << coinChange(coins, 11) << endl; // Output: 2
    return 0;
}

Time: O(amount × |coins|)   Space: O(amount)

8.3 — House Robber

Problem: You're a robber planning to rob houses along a street. You cannot rob two adjacent houses (alarm triggers). Maximise the total loot.

State: dp[i] = maximum money by considering houses 0 to i.

Recurrence: dp[i] = max(dp[i-1], dp[i-2] + money[i])

Base cases: dp[0] = money[0], dp[1] = max(money[0], money[1])

DP Table Trace: houses = {2, 7, 9, 3, 1}

dp[0]=2. dp[1]=max(2,7)=7. dp[2]=max(7, 2+9)=11. dp[3]=max(11, 7+3)=11. dp[4]=max(11, 11+1)=12. Rob houses 0, 2, 4 (₹2+₹9+₹1=₹12).

C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int houseRobber(vector<int>& money) {
    int n = money.size();
    if (n == 0) return 0;
    if (n == 1) return money[0];
    vector<int> dp(n);
    dp[0] = money[0];
    dp[1] = max(money[0], money[1]);
    for (int i = 2; i < n; i++)
        dp[i] = max(dp[i - 1], dp[i - 2] + money[i]);
    return dp[n - 1];
}

int main() {
    vector<int> houses = {2, 7, 9, 3, 1};
    cout << "Max loot: " << houseRobber(houses) << endl; // Output: 12
    return 0;
}

Time: O(n)   Space: O(n) → can optimise to O(1) with two variables.

8.4 — Min Cost Path in Grid

Problem: Given an m×n grid where each cell has a cost, find the path from top-left to bottom-right with minimum total cost. You can only move right or down.

State: dp[i][j] = minimum cost to reach cell (i, j).

Recurrence: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

Base cases: dp[0][0] = grid[0][0]. First row and first column are cumulative sums.

DP Table Trace: grid = {{1,3,1},{1,5,1},{4,2,1}}

dp[0][1]=1+3=4, dp[0][2]=4+1=5. dp[1][0]=1+1=2, dp[1][1]=5+min(4,2)=7, dp[1][2]=1+min(5,7)=6. dp[2][0]=4+2=6, dp[2][1]=2+min(7,6)=8, dp[2][2]=1+min(6,8)=7. Path: 1→3→1→1→1.

C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minCostPath(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n));
    dp[0][0] = grid[0][0];
    // Fill first row
    for (int j = 1; j < n; j++)
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    // Fill first column
    for (int i = 1; i < m; i++)
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    // Fill rest of DP table
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
    return dp[m - 1][n - 1];
}

int main() {
    vector<vector<int>> grid = {{1,3,1},{1,5,1},{4,2,1}};
    cout << "Min cost: " << minCostPath(grid) << endl; // Output: 7
    return 0;
}

Time: O(m×n)   Space: O(m×n) → can optimise to O(n) by reusing a single row.

Learn by Doing — 3-Tier Lab Structure

Problem Set — Practice & Mastery

Part 1: DP Table Tracing (5 Problems)

Fill in the complete DP table for each problem. Show your work step-by-step.

T1. Fill the DP table for Fibonacci(8)

T2. Fill the DP table for Climbing Stairs(7)

T3. Fill the DP table for Coin Change: amount=15, coins={1,5,10}

T4. Fill the DP table for House Robber: houses = {3, 1, 4, 1, 5, 9}

T5. Fill the DP table for Min Cost Path: grid = {{2,1,3},{6,5,4},{7,8,9}}

Part 2: Programming Problems (8 Problems)

Implement each in C/C++. Provide time and space complexity.

1. P1. Fibonacci N-th Term — Compute the n-th Fibonacci number using tabulation. Beginner
2. P2. Extended Climbing Stairs — Count ways to climb n stairs with steps of 1, 2, or 3 at a time. Beginner
3. P3. Coin Change (Min Coins) — Given denominations and an amount, find minimum coins needed. Intermediate
4. P4. House Robber (Circular) — Houses are arranged in a circle (first and last are adjacent). Find max loot. Intermediate
5. P5. Min Cost Path with Obstacles — Same as min cost path, but some cells are blocked (cost = -1). Intermediate
6. P6. Longest Increasing Subsequence — Find the length of the LIS in an array. Intermediate
7. P7. 0/1 Knapsack Problem — Given weights and values, maximise value within weight capacity. Advanced
8. P8. Edit Distance — Find minimum operations (insert, delete, replace) to convert one string to another. Advanced

Part 3: Industry Application Problems (3 Problems)

1. I1. Paytm Cashback Optimiser: Given N cashback offers, each with a value and a set of conflicting offers (can't use together), find the maximum total cashback a user can redeem. (Variant of weighted independent set / knapsack.)
2. I2. Amazon Delivery Route: A city is represented as an m×n grid. Each cell has a fuel cost. Some cells are blocked (construction). Find the minimum fuel cost route from the warehouse (0,0) to the customer (m-1, n-1).
3. I3. Flipkart Warehouse Allocation: Flipkart has K warehouses, each with a storage cost per unit. N products need to be stored. Minimise total storage cost such that no warehouse exceeds capacity. (Variant of bin packing / knapsack.)

Part 4: Interview Problems (3 Problems)

1. V1. Google — Maximum Subarray Sum: Given an integer array, find the contiguous subarray with the largest sum. Implement Kadane's algorithm as a DP solution. State: dp[i] = max subarray sum ending at index i.
2. V2. Amazon — Word Break: Given a string and a dictionary of words, determine if the string can be segmented into space-separated sequence of dictionary words. State: dp[i] = true if s[0..i-1] can be segmented.
3. V3. Microsoft — Decode Ways: Given a string of digits, count the number of ways to decode it (A=1, B=2, …, Z=26). State: dp[i] = number of ways to decode s[0..i-1].

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

Remember / Identify (Q1–Q5)

Understand / Explain (Q6–Q10)

Apply (Q11–Q15)

Analyze (Q16–Q20)

Evaluate (Q21–Q25)

Create (Q26–Q30)

Short Answer Questions (8 Questions)

                    F(5)
                   /    \
                F(4)    F(3)  ← REPEATED
               /   \    /  \
            F(3)  F(2) F(2) F(1)  ← F(2) REPEATED
           /  \
         F(2) F(1)  ← F(2) REPEATED

Long Answer Questions (3 Questions)

C++
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
    vector<int> coins = {1,5,6,9};
    int amount = 11;
    vector<int> dp(amount+1, INT_MAX);
    dp[0] = 0;
    for(int i=1; i<=amount; i++)
        for(int c : coins)
            if(c<=i && dp[i-c]!=INT_MAX)
                dp[i] = min(dp[i], dp[i-c]+1);
    cout << dp[amount] << endl; // Output: 2
}

C++
// After building DP table, backtrack from (m-1,n-1) to (0,0)
void printPath(vector<vector<int>>& dp, int m, int n) {
    vector<pair<int,int>> path;
    int i = m-1, j = n-1;
    path.push_back({i, j});
    while (i > 0 || j > 0) {
        if (i == 0) j--;
        else if (j == 0) i--;
        else if (dp[i-1][j] < dp[i][j-1]) i--;
        else j--;
        path.push_back({i, j});
    }
    for (int k = path.size()-1; k >= 0; k--)
        cout << "(" << path[k].first << "," << path[k].second << ") ";
}

C++
// 1. Recursive
int fibRec(int n) {
    if(n<=1) return n;
    return fibRec(n-1) + fibRec(n-2);
}

// 2. Memoized
int memo[1000001];
int fibMemo(int n) {
    if(n<=1) return n;
    if(memo[n]!=-1) return memo[n];
    return memo[n] = fibMemo(n-1) + fibMemo(n-2);
}

// 3. Tabulated
int fibTab(int n) {
    if(n<=1) return n;
    int dp[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];
}

C++
long long fibOpt(int n) {
    if(n<=1) return n;
    long long prev2 = 0, prev1 = 1, curr;
    for(int i=2; i<=n; i++) {
        curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Lab Program — Tiling Problem

C++
#include <iostream>
using namespace std;

int tilingWays(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;

    int dp[n + 1];
    dp[1] = 1;
    dp[2] = 2;

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

    return dp[n];
}

int main() {
    int n;
    cout << "Enter the value of n: ";
    cin >> n;

    cout << "Number of ways to tile a 2x" << n
         << " board: " << tilingWays(n) << endl;

    // Print DP table for reference
    cout << "\nDP Table:\n";
    cout << "n\t| Ways\n";
    cout << "--------|------\n";
    for (int i = 1; i <= n; i++) {
        cout << i << "\t| " << tilingWays(i) << "\n";
    }

    return 0;
}

Industry Spotlight — A Day in the Life

Earn With It — Freelance & Income Roadmap

⏱️ Time to First Earning: 1–2 weeks (if you can solve 50+ DP problems confidently and create a Topmate profile)

Chapter Summary

Earning Checkpoint

✅ Unit 4 complete. Ready for Unit 5: Advanced DP Techniques!

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