Greedy vs DP How to Know Which to Apply in DSA C - Trade-offs & Analysis

Mental Model

Greedy picks the best choice now, hoping it leads to the best overall. DP tries all choices carefully and remembers results to find the best overall.

Analogy: Choosing snacks: greedy is like grabbing the tastiest snack first without thinking ahead; DP is like planning all snacks to get the tastiest total meal.

Choices: [1] -> [2] -> [3] -> [4] -> null
Greedy: picks one step at a time ->
DP: explores all paths and remembers best results ↑

Dry Run Walkthrough

Input: Problem: Maximize sum by picking numbers from list [3, 2, 7, 10], no two adjacent picks allowed.

Goal: Decide if greedy or DP works and find max sum.

Step 1: Try greedy: pick biggest number first (10)

Picked 10, skip adjacent 7
Remaining picks: [3, 2]

Why: Greedy picks biggest now, but may miss better total.

Step 2: Greedy picks next biggest (3)

Picked 10 and 3
Sum = 13

Why: Greedy picks locally best but may not be global best.

Step 3: Try DP: check all combinations without adjacent picks

Options: (3 + 7) = 10, (3 + 10) = 13, (2 + 10) = 12

Why: DP explores all valid picks and remembers best sums.

Step 4: DP finds max sum is 13 (3 + 10)

Max sum = 13

Why: DP guarantees best total by checking all choices.

Result:

Max sum = 13 by picking 3 and 10; greedy works here but DP confirms best.

Annotated Code

DSA C

#include <stdio.h>

// Function to find max sum with no two adjacent picks using DP
int max(int a, int b) {
    return (a > b) ? a : b;
}

int maxSumNoAdjacent(int arr[], int n) {
    if (n == 0) return 0;
    if (n == 1) return arr[0];

    int dp[n];
    dp[0] = arr[0];
    dp[1] = max(arr[0], arr[1]);

    for (int i = 2; i < n; i++) {
        // Either pick current + dp[i-2] or skip current and take dp[i-1]
        dp[i] = max(arr[i] + dp[i-2], dp[i-1]);
    }
    return dp[n-1];
}

int main() {
    int arr[] = {3, 2, 7, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    int result = maxSumNoAdjacent(arr, n);
    printf("Max sum with no two adjacent picks: %d\n", result);

    return 0;
}

dp[0] = arr[0];

initialize dp with first element as base case

dp[1] = max(arr[0], arr[1]);

choose max of first two elements as second base case

dp[i] = max(arr[i] + dp[i-2], dp[i-1]);

choose max between picking current plus dp[i-2] or skipping current

Output

Max sum with no two adjacent picks: 13

Complexity Analysis

Time: O(n) because we fill dp array once for n elements

Space: O(n) for dp array storing max sums up to each index

vs Alternative: Greedy is faster but may fail; DP is slower but always correct for overlapping subproblems

Edge Cases

Empty list

Returns 0 as no picks possible

DSA C

if (n == 0) return 0;

Single element list

Returns that element as max sum

DSA C

if (n == 1) return arr[0];

All elements equal

Returns sum of alternate elements correctly

DSA C

dp[i] = max(arr[i] + dp[i-2], dp[i-1]);

When to Use This Pattern

When a problem asks for optimal choices with constraints and overlapping subproblems, try DP; if local best choices always lead to global best, greedy works.

Common Mistakes

Mistake: Assuming greedy always works without checking problem constraints
Fix: Test small cases or use DP to confirm if greedy is valid

Mistake: Not handling base cases in DP leading to wrong results
Fix: Explicitly set dp[0] and dp[1] before loop

Summary

Greedy picks the best immediate choice; DP tries all choices and remembers results.

Use greedy when local choices guarantee global best; use DP when overlapping subproblems exist.

The key is to check if greedy's local best leads to global best; if unsure, use DP.