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.