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.

Practice

1. Which of the following best describes when to use a greedy algorithm instead of dynamic programming?

easy

A. When the problem has the greedy choice property and optimal substructure

B. When the problem requires checking all possible combinations

C. When the problem has overlapping subproblems but no greedy choice

D. When the problem is about sorting large datasets

Solution

1. Step 1: Understand greedy choice property

   A greedy algorithm works when choosing the best option at each step leads to a global optimum.

2. Step 2: Compare with dynamic programming conditions

   Dynamic programming is used when subproblems overlap and greedy choice property does not hold.

3. Final Answer:

   When the problem has the greedy choice property and optimal substructure -> Option A

4. Quick Check:

   Greedy choice property = Use greedy [OK]

Hint: Use greedy if local best leads to global best [OK]

Common Mistakes:

• Confusing overlapping subproblems with greedy choice
• Using greedy when problem needs full exploration
• Assuming sorting problems always need greedy

2. Which of the following is the correct syntax to declare a memoization array for dynamic programming in C?

easy

A. int memo[1000] = {0};

B. int memo[] = 0;

C. int memo(1000) = {0};

D. int memo = new int[1000];

Solution

1. Step 1: Recall C array declaration syntax

   In C, arrays are declared with fixed size and optional initialization using braces.

2. Step 2: Check each option

   int memo[1000] = {0}; correctly declares an int array of size 1000 initialized to zero. Others are invalid C syntax.

3. Final Answer:

   int memo[1000] = {0}; -> Option A

4. Quick Check:

   C arrays use [] with size [OK]

Hint: Use int arr[size] = {0} for zero-initialized arrays [OK]

Common Mistakes:

• Using parentheses instead of brackets for arrays
• Trying to assign 0 directly to array
• Using new keyword in C (it's C++ syntax)

3. What is the output of the following C code snippet that uses a greedy approach to select coins?

int coins[] = {1, 5, 10, 25};
int amount = 30;
int count = 0;
for (int i = 3; i >= 0; i--) {
    while (amount >= coins[i]) {
        amount -= coins[i];
        count++;
    }
}
printf("%d\n", count);

medium

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Trace the greedy coin selection

   Start with coin 25: amount=30, 30>=25, subtract 25, amount=5, count=1.

2. Step 2: Continue with smaller coins

   Next coin 10: amount=5<10, skip. Next coin 5: amount=5>=5, subtract 5, amount=0, count=2.

3. Step 3: No more coins needed

   Loop ends, total coins used = 2.

4. Final Answer:

   2 -> Option C

5. Quick Check:

   25 + 5 = 30 using 2 coins [OK]

Hint: Subtract largest coin repeatedly until amount zero [OK]

Common Mistakes:

• Counting coins incorrectly in loops
• Not updating amount after subtraction
• Confusing coin order in loop

4. The following code attempts to solve the Fibonacci sequence using a greedy approach. What is the error?

int fib(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c = 0;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

medium

A. Loop should start from i = 1 instead of 2

B. No error, code correctly computes Fibonacci

C. Variable c is not initialized properly

D. Greedy approach is incorrect for Fibonacci calculation

Solution

1. Step 1: Understand Fibonacci calculation

   Fibonacci requires summing previous two numbers, which is a classic dynamic programming problem.

2. Step 2: Identify greedy approach misuse

   The code uses iteration correctly but calling it greedy is wrong because Fibonacci does not have greedy choice property.

3. Final Answer:

   Greedy approach is incorrect for Fibonacci calculation -> Option D

4. Quick Check:

   Fibonacci needs DP, not greedy [OK]

Hint: Fibonacci needs DP, greedy won't work [OK]

Common Mistakes:

• Thinking iterative is greedy
• Ignoring problem properties
• Confusing initialization with error

5. You want to find the minimum number of coins to make change for a given amount using coins of denominations {1, 3, 4}. Which approach is best and why?

hard

A. Greedy, because always picking the largest coin works here

B. Dynamic Programming, because greedy fails for some amounts

C. Brute force, because both greedy and DP are too complex

D. Sorting coins and picking smallest first

Solution

1. Step 1: Test greedy approach on example

   For amount 6, greedy picks 4 + 1 + 1 = 3 coins, but optimal is 3 + 3 = 2 coins.

2. Step 2: Recognize overlapping subproblems

   Dynamic programming stores solutions for smaller amounts to build up answer correctly.

3. Step 3: Conclude best approach

   Greedy fails due to lack of greedy choice property; DP handles all cases optimally.

4. Final Answer:

   Dynamic Programming, because greedy fails for some amounts -> Option B

5. Quick Check:

   Greedy fails, DP works [OK]

Hint: Test greedy on small cases; if fails, use DP [OK]

Common Mistakes:

• Assuming greedy always works for coin change
• Ignoring counterexamples
• Choosing brute force unnecessarily