Greedy vs DP How to Know Which to Apply in DSA C - Compare & Choose

Challenge - 5 Problems

🧠 Conceptual

intermediate

When to Choose Greedy Over Dynamic Programming?

Which of the following problem characteristics best indicates that a greedy approach is suitable instead of dynamic programming?

A The problem requires storing results of subproblems to avoid recomputation.

B The problem has overlapping subproblems and requires exploring all combinations.

C The problem involves complex state transitions and multiple decision paths.

D The problem has an optimal substructure and making locally optimal choices leads to a global optimum.

💡 Hint

Think about when making the best choice at each step guarantees the best overall solution.

Greedy algorithms work well when the problem has an optimal substructure and making the best local choice at each step leads to the global optimum. Dynamic programming is needed when overlapping subproblems require storing intermediate results.

❓ Predict Output

intermediate

Output of Coin Change Problem Using Greedy Approach

What is the output of the following C code that tries to make change for 30 using coins of 25, 10, and 5 cents with a greedy approach?

DSA C

int coins[] = {25, 10, 5};
int amount = 30;
int i = 0;
while (amount > 0) {
    if (amount >= coins[i]) {
        printf("%d ", coins[i]);
        amount -= coins[i];
    } else {
        i++;
    }
}

A 25 5

B 10 10 10

C 25 10

D 5 5 5 5 5 5

💡 Hint

Trace how the greedy picks the largest coin first until it cannot.

The greedy approach picks 25 first (amount becomes 5), then picks 5. So output is '25 5 '.

❓ Predict Output

advanced

Dynamic Programming Table for Fibonacci Sequence

What is the content of the DP array after running this C code to compute Fibonacci(5)?

DSA C

int fib[6];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= 5; i++) {
    fib[i] = fib[i-1] + fib[i-2];
}
for (int i = 0; i <= 5; i++) {
    printf("%d ", fib[i]);
}

A 1 1 2 3 5 8

B 0 1 1 2 3 5

C 0 1 2 3 5 8

D 0 1 1 3 5 8

💡 Hint

Recall Fibonacci starts with 0 and 1, then sums previous two.

The DP array stores Fibonacci numbers from 0 to 5: 0,1,1,2,3,5,8.

🧠 Conceptual

advanced

Why Dynamic Programming is Needed Over Greedy in Some Problems?

Which reason best explains why dynamic programming is necessary instead of greedy for some optimization problems?

A Because dynamic programming uses less memory than greedy algorithms.

B Because greedy algorithms always produce incorrect results.

C Because some problems have overlapping subproblems and require considering multiple future choices.

D Because greedy algorithms cannot be implemented in C language.

💡 Hint

Think about when local choices are not enough to guarantee the best overall solution.

Dynamic programming is needed when problems have overlapping subproblems and the best solution depends on multiple future decisions, which greedy cannot handle.

🚀 Application

expert

Choosing Algorithm for Job Scheduling with Deadlines and Profits

You have jobs with deadlines and profits. You want to schedule jobs to maximize total profit without missing deadlines. Which approach is best?

A Use a greedy algorithm that sorts jobs by profit and schedules them as late as possible before deadline.

B Use dynamic programming to explore all subsets of jobs and pick the best combination.

C Use a simple loop to schedule jobs in the order they appear without sorting.

D Use a divide and conquer approach to split jobs and merge schedules.

💡 Hint

Think about how to pick jobs with highest profit first and place them optimally.

The classic job scheduling with deadlines and profits problem is solved efficiently with a greedy approach that sorts jobs by profit and schedules them as late as possible before their deadline.

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