DYNAMIC PROGRAMMING IN C

Dynamic Programming Fundamentals

What is Dynamic Programming?

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them down into simpler subproblems, storing the results of these subproblems to avoid redundant computations.

Optimal Substructure - Solution can be constructed from optimal solutions to subproblems
Overlapping Subproblems - Problem can be broken down into subproblems which are reused several times
Memoization - Top-down approach with caching
Tabulation - Bottom-up approach with table building

When to Use Dynamic Programming

DP is appropriate when you can identify:

Problems that can be divided into overlapping subproblems
Recursive solutions with repeated computations
Optimization problems (min/max, shortest/longest paths, etc.)
Counting problems (number of ways to do something)
Problems where greedy approaches fail

Common indicators: "Count the number of ways", "Find the minimum/maximum", "Is it possible to..."

DP Approaches

Top-Down (Memoization)

Recursive approach with caching
More intuitive but has recursion overhead
Only computes necessary subproblems
Easier to implement for some problems

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

Bottom-Up (Tabulation)

Iterative approach with table building
No recursion overhead
Often more space-efficient
Better for understanding dependencies

int fib(int 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];
}

DYNAMIC PROGRAMMING TECHNIQUES

#	Technique	Use Case	Approach	Complexity	Examples
1	1D DP	Problems with single changing parameter	Use 1D array where dp[i] represents solution for subproblem of size i	O(n) O(n)	Fibonacci series Climbing stairs House robber Maximum subarray
2	2D DP	Problems with two changing parameters	Use 2D array where dp[i][j] represents solution for subproblem with parameters i and j	O(n²) O(n²)	Longest common subsequence Edit distance Knapsack problem Matrix chain multiplication
3	State Machine	Problems with multiple states or choices at each step	Model states and transitions between them, track multiple DP arrays	O(n) O(n)	Buy/sell stock with cooldown House robber with constraints State-dependent paths
4	Bitmask DP	Problems with subsets or permutations	Use bitmask to represent subsets, dp[mask] stores solution for subset	O(n2ⁿ) O(2ⁿ)	TSP (Traveling Salesman) Assignment problem Subset problems
5	DP on Trees	Tree-related optimization problems	Post-order traversal, compute DP values from children to parent	O(n) O(n)	Diameter of tree Maximum path sum House robber III
6	Prefix/Suffix DP	Problems with cumulative operations	Precompute prefix/suffix arrays to store intermediate results	O(n) O(n)	Maximum product subarray Trapping rain water Maximum sum circular subarray
7	DP + Binary Search	Optimization problems with monotonicity	Combine DP with binary search to optimize solution space	O(n log n) O(n)	Longest increasing subsequence Split array largest sum Minimum difficulty job schedule

Common DP Patterns with C Examples

Fibonacci Sequence

The classic DP problem demonstrating overlapping subproblems.

int fib(int 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];
}

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

0/1 Knapsack

Select items with maximum value without exceeding weight capacity.

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

Time: O(nW), Space: O(nW)

Longest Common Subsequence

Find the longest sequence present in both strings.

int lcs(char *X, char *Y, int m, int n) {
    int dp[m+1][n+1];
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) dp[i][j] = 0;
            else 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];
}

Time: O(mn), Space: O(mn)

Coin Change

Minimum number of coins to make a given amount.

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

Time: O(n*amount), Space: O(amount)

Edit Distance

Minimum operations to convert one string to another.

int editDistance(char *word1, char *word2) {
    int m = strlen(word1), n = strlen(word2);
    int dp[m+1][n+1];
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0) dp[i][j] = j;
            else if (j == 0) dp[i][j] = i;
            else if (word1[i-1] == word2[j-1])
                dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = 1 + min(dp[i][j-1], 
                                   min(dp[i-1][j], 
                                       dp[i-1][j-1]));
        }
    }
    return dp[m][n];
}

Time: O(mn), Space: O(mn)

Longest Increasing Subsequence

Find length of longest subsequence in increasing order.

int lengthOfLIS(int nums[], int n) {
    int dp[n], max_len = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++)
            if (nums[i] > nums[j] && dp[i] < dp[j] + 1)
                dp[i] = dp[j] + 1;
        max_len = max(max_len, dp[i]);
    }
    return max_len;
}

Time: O(n²), Space: O(n)

DP Optimization Techniques

#	Technique	Description	When to Use
1	Space Optimization	Reduce space complexity by reusing or eliminating parts of the DP table	When only previous row/state is needed
2	State Compression	Use bitmask or other compact representations to store state	Problems with small state spaces
3	Knuth's Optimization	Optimize certain DP problems with quadrangle inequalities	DP problems with specific cost functions
4	Convex Hull Trick	Optimize DP transitions of the form dp[i] = min/max(dp[j] + cost(j,i))	When transitions can be modeled as linear functions
5	Divide and Conquer	Optimize certain DP problems by splitting the problem space	When monotonicity conditions are satisfied
6	Monotonic Queue	Optimize sliding window minimum/maximum problems	When transitions involve sliding window minima/maxima

Related DP Resources

Basic Programs

Interview Questions

MCQs

DP Notes