Dynamic Programming in C

Dynamic Programming (DP): From Beginner to Advanced

Dynamic Programming often strikes fear into the hearts of candidates, yet it remains the ultimate key to passing advanced coding interviews. Experienced developers master DP by recognizing patterns rather than memorizing code. In this comprehensive guide, we will break down the exact syllabus, coding patterns, and problems you need to conquer DP.

1. What is Dynamic Programming?

Dynamic Programming is an algorithmic optimization technique that saves your program from executing the exact same mathematical operations multiple times. You apply DP when a problem satisfies two strict conditions:

• Overlapping Subproblems: The overall problem breaks down into identical, smaller problems that the computer solves repeatedly. For example, to calculate $fib(5)$, the computer must calculate $fib(3)$ multiple times across different branches of the recursive tree.
• Optimal Substructure: You can build the absolute, perfect solution for a massive problem strictly by combining the perfect solutions of its smaller subproblems. For example: $fib(5) = fib(4) + fib(3)$.

2. The Three DP Approaches

Software engineers approach these mathematical obstacles using three distinct methodologies:

• Pure Recursion: The brute-force mathematical approach. It evaluates every possible branch, resulting in extremely slow, exponential time complexities like $O(2^N)$.
• Memoization (Top-Down): You execute standard recursion, but you cache the answers in an array (like $dp[n]$) the first time you solve them. Before doing math, you check the cache: if(dp[n] != -1) return dp[n];. This drops the time complexity instantly to $O(N)$.
• Tabulation (Bottom-Up): You abandon recursion entirely. Instead, you start from the absolute base cases (like $dp[0]$ and $dp[1]$) and use a standard for loop to build your answers upward toward $dp[n]$. Interviewers overwhelmingly prefer Tabulation because it avoids stack overflow memory issues.

3. The DP Identification Checklist

How do you know an interview question requires Dynamic Programming? Look for specific keywords in the prompt. If the interviewer asks you to evaluate:

• Count the total number of Ways
• Find the Minimum Cost
• Find the Maximum Profit
• Calculate the Longest or Shortest path/sequence
• Find the absolute Optimal Solution

---

4. Beginner Level DP

Problem 1: Fibonacci Number

The most foundational DP problem in computer science. The state of the current number relies entirely on the previous two states: $fib(n) = fib(n-1) + fib(n-2)$.

// Optimized Tabulation (Bottom-Up) Approach in C
#include <stdio.h>

int main() {
    int n = 10;
    int dp[100];

    // Base cases
    dp[0] = 0;
    dp[1] = 1;

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

    printf("%d", dp[n]);
    return 0;
}

Problem 2: Climbing Stairs

A famous LeetCode problem. You can climb 1 step or 2 steps at a time. How many distinct ways can you reach the Nth stair? To reach stair 5, your very last move could strictly be a 1-step move from stair 4, or a 2-step move from stair 3. Therefore, the transition formula is $dp[i] = dp[i-1] + dp[i-2]$.

#include <stdio.h>

int main() {
    int n = 5;
    int dp[100];

    // Base cases
    dp[0] = 1; // 1 way to stay at the ground
    dp[1] = 1; // 1 way to reach the first step

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

    printf("%d", dp[n]);
    return 0;
}

---

5. Intermediate DP

Problem 3: The 0/1 Knapsack

The crown jewel of Dynamic Programming. You have a backpack with a maximum weight capacity, and a list of items holding specific weights and profit values. You must maximize your profit. Because it is a "0/1" problem, you face a binary choice for every single item: Take it, or Exclude it.

We represent the state as $dp[i][w]$, which maps the maximum profit using the first $i$ items strictly within weight limit $w$. The transition logic checks if the item fits. If it does, we evaluate $dp[i][w] = \max(\text{take item}, \text{skip item})$.

#include <stdio.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int main() {
    int wt[] = {10, 20, 30};
    int val[] = {60, 100, 120};
    int W = 50, n = 3;
    int dp[4][51];

    for(int i = 0; i <= n; i++) {
        for(int w = 0; w <= W; w++) {
            if(i == 0 || w == 0) {
                dp[i][w] = 0; // Base case
            } else if(wt[i-1] <= w) {
                // Item fits: Check max between taking and leaving
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]);
            } else {
                // Item is too heavy: Leave it
                dp[i][w] = dp[i-1][w];
            }
        }
    }

    printf("Max Profit: %d\n", dp[n][W]);
    return 0;
}

Problem 4: Coin Change

Given coins [1, 2, 5] and a target amount of 11, find the minimum number of coins needed. We evaluate state $dp[i]$, which denotes the minimum coins needed for amount $i$. The mathematical transition scans every available coin size to find the optimal previous state: $dp[i] = \min(dp[i-coin] + 1)$.

#include <stdio.h>
#include <limits.h>

int main() {
    int coins[] = {1, 2, 5};
    int amount = 11;
    int dp[100];

    // Initialize array with infinity
    for(int i = 0; i <= amount; i++) dp[i] = INT_MAX;
    dp[0] = 0; // Base case

    for(int i = 1; i <= amount; i++) {
        for(int j = 0; j < 3; j++) {
            if(i >= coins[j] && dp[i-coins[j]] != INT_MAX) {
                if(dp[i] > dp[i-coins[j]] + 1) {
                    dp[i] = dp[i-coins[j]] + 1;
                }
            }
        }
    }

    printf("Minimum Coins: %d\n", dp[amount]);
    return 0;
}

---

6. Advanced DP Concepts

Matrix Chain Multiplication (MCM)

The definitive Partition DP pattern. Given matrices A, B, C, and D, you must find the parenthesization path, like $(AB)(CD)$ or $A(BCD)$, that yields the absolute minimum multiplication operations cost. The state evaluates $dp[i][j]$ as the minimum cost to multiply matrices from index $i$ to $j$. The transition formula searches for the optimal splitting point $k$:
$dp[i][j] = \min(dp[i][k] + dp[k+1][j] + cost)$

Longest Increasing Subsequence (LIS)

You evaluate state $dp[i]$, holding the length of the LIS explicitly ending at index $i$. For all previous elements $j$, if $arr[j] < arr[i]$, then the transition updates the sequence: $dp[i] = \max(dp[i], dp[j] + 1)$. While standard 1D DP solves this in $O(N^2)$, advanced developers merge this logic with Binary Search to achieve $O(N \log N)$ execution speeds.

---

7. Most Important DP Interview Patterns

Algorithmic Pattern	Common Core Problems
1. Fibonacci DP	Climbing Stairs, House Robber
2. Take / Not Take	0/1 Knapsack, Subset Sum, Partition Equal Subset
3. Unbounded Choice	Coin Change, Rod Cutting
4. String DP (2D)	Longest Common Subsequence (LCS), Edit Distance
5. Partition DP	MCM, Burst Balloons, Palindrome Partitioning
6. Sequence DP	Longest Increasing Subsequence (LIS), Russian Doll Envelopes

The Definitive DP Interview Roadmap

If you are an engineer aiming for premium backend roles, master these specific problems in order. If you can clearly explain the State, Transition, Base Case, Memoization, and Tabulation approaches for these exact problems, you will conquer almost any DP question thrown at you.

Phase 1: Beginner (State Relationships)

Fibonacci → Climbing Stairs → Min Cost Climbing Stairs → House Robber

Phase 2: Intermediate (Binary Choices & Unbounded)

0/1 Knapsack → Subset Sumc→ Equal Partition → Coin Change → Rod Cutting

Phase 3: Strings & Sequences

Longest Common Subsequence (LCS) → Longest Common Substring → Edit Distance → LIS

Phase 4: Advanced (Partitioning & Trees)

Matrix Chain Multiplication (MCM) → Palindrome Partitioning → Burst Balloons → DP on Trees → Bitmask DP