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?

You have a problem where you need to find the minimum number of coins to make a certain amount using given coin denominations. Which approach is best and why?

A Use DP only if the problem size is very small; otherwise use Greedy.

B Use Greedy if the coin denominations are canonical (like 1, 5, 10, 25), otherwise use DP.

C Always use Greedy because it is faster and simpler than DP.

D Use DP only when the problem involves sorting the coins first.

💡 Hint

Think about whether a local choice leads to a global optimum.

Greedy works when the problem has the greedy-choice property, such as canonical coin systems. Otherwise, DP is needed to explore all combinations.

❓ Predict Output

intermediate

Output of Greedy vs DP on Activity Selection

What is the output of the following C++ code that selects maximum activities using Greedy and DP?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Activity {
    int start, finish;
};

bool activityCompare(Activity s1, Activity s2) {
    return (s1.finish < s2.finish);
}

int greedyActivitySelector(vector<Activity> &activities) {
    sort(activities.begin(), activities.end(), activityCompare);
    int count = 1;
    int last_finish = activities[0].finish;
    for (int i = 1; i < activities.size(); i++) {
        if (activities[i].start >= last_finish) {
            count++;
            last_finish = activities[i].finish;
        }
    }
    return count;
}

int main() {
    vector<Activity> activities = {{1,4}, {3,5}, {0,6}, {5,7}, {8,9}, {5,9}};
    cout << greedyActivitySelector(activities) << endl;
    return 0;
}

A 4

B 3

C 5

D 6

💡 Hint

Count how many activities can be selected without overlapping using earliest finish time.

The greedy approach selects activities by earliest finish time, allowing 4 activities to be selected.

🔧 Debug

advanced

Why does this DP solution for Knapsack fail to give correct answer?

Consider this DP code for 0/1 Knapsack. It returns wrong maximum value. What is the bug?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

int knapsack(int W, vector<int> &wt, vector<int> &val, int n) {
    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            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];
}

int main() {
    vector<int> wt = {1, 3, 4, 5};
    vector<int> val = {1, 4, 5, 7};
    int W = 7;
    cout << knapsack(W, wt, val, wt.size()) << endl;
    return 0;
}

A The max function is used incorrectly; should use min instead.

B The dp table is not initialized with -1 for memoization.

C Indexing wt and val from 1 causes out-of-range errors; should start from 0.

D The weight comparison uses <= but should use <.

💡 Hint

Check how arrays wt and val are accessed inside the loops.

Arrays wt and val are zero-indexed but code accesses wt[i], val[i] starting from i=1, causing wrong values or out-of-range access.

❓ Predict Output

advanced

Output of code comparing Greedy and DP for Coin Change

What is the output of this C++ code that compares greedy and DP solutions for coin change amount 6 with coins {1,3,4}?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int greedyCoinChange(vector<int> &coins, int amount) {
    sort(coins.rbegin(), coins.rend());
    int count = 0;
    for (int coin : coins) {
        while (amount >= coin) {
            amount -= coin;
            count++;
        }
    }
    if (amount != 0) return -1;
    return count;
}

int dpCoinChange(vector<int> &coins, int amount) {
    vector<int> dp(amount+1, amount+1);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

int main() {
    vector<int> coins = {1, 3, 4};
    int amount = 6;
    cout << greedyCoinChange(coins, amount) << " " << dpCoinChange(coins, amount) << endl;
    return 0;
}

A 6 2

B -1 2

C 2 2

D 3 3

💡 Hint

Trace greedy picking largest coins first and DP finding minimum coins.

Greedy picks 4+1+1=3 coins but code counts 6 coins because it subtracts 1 repeatedly after 4. DP finds minimum 2 coins (3+3).

🧠 Conceptual

expert

Which problem property guarantees Greedy works instead of DP?

Which property of a problem ensures that a greedy algorithm will always produce an optimal solution, making dynamic programming unnecessary?

A No subproblems and no optimal substructure

B Optimal substructure and overlapping subproblems

C Only overlapping subproblems

D Greedy-choice property and optimal substructure

💡 Hint

Think about what makes a local choice lead to a global optimum.

Greedy algorithms require the greedy-choice property (local optimal choices lead to global optimum) and optimal substructure (optimal solution contains optimal subsolutions).

Practice

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

easy

A. When the problem has no clear optimal substructure

B. When the problem has optimal substructure and no overlapping subproblems

C. When the problem requires checking all possible solutions

D. When the problem has overlapping subproblems and optimal substructure

Solution

1. Step 1: Understand greedy algorithm conditions

   Greedy algorithms work well when the problem has an optimal substructure and no overlapping subproblems, meaning making the best local choice leads to a global optimum.

2. Step 2: Compare with dynamic programming conditions

   Dynamic programming is used when there are overlapping subproblems and optimal substructure, requiring storing intermediate results to avoid recomputation.

3. Final Answer:

   When the problem has optimal substructure and no overlapping subproblems -> Option B

4. Quick Check:

   Greedy = optimal substructure + no overlap [OK]

Hint: Use greedy if no overlapping subproblems exist [OK]

Common Mistakes:

• Confusing overlapping subproblems as a greedy condition
• Using DP when greedy suffices
• Ignoring optimal substructure requirement

2. Which of the following C++ code snippets correctly initializes a DP array for a problem with 5 states?

easy

A. int dp[5];

B. int dp(5, 0);

C. vector<int> dp(5, 0);

D. int dp = new int[5];

Solution

1. Step 1: Check syntax for array initialization

   int dp[5]; leaves elements uninitialized. int dp(5, 0); is invalid syntax for array initialization. int dp = new int[5]; uses incorrect syntax and memory management in C++.

2. Step 2: Identify correct vector initialization

   vector<int> dp(5, 0); correctly creates a vector of size 5 with all elements initialized to 0, which is the preferred way to initialize DP arrays in modern C++.

3. Final Answer:

   vector<int> dp(5, 0); -> Option C

4. Quick Check:

   Use vector<int> dp(size, 0) for DP arrays [OK]

Hint: Use vector with size and initial value for DP arrays [OK]

Common Mistakes:

• Using incorrect syntax for array initialization
• Not initializing all elements to zero
• Using raw pointers without delete

3. Consider the following C++ code snippet for a problem that can be solved by either greedy or DP. What is the output?

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = 5;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 == 0) {
            sum += arr[i];
        }
    }
    std::cout << sum << std::endl;
    return 0;
}

medium

A. 6

B. 9

C. 15

D. 10

Solution

1. Step 1: Identify even numbers in the array

   The array is {1, 2, 3, 4, 5}. Even numbers are 2 and 4.

2. Step 2: Calculate sum of even numbers

   Sum = 2 + 4 = 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Sum of even numbers = 6 [OK]

Hint: Sum only even numbers using modulo check [OK]

Common Mistakes:

• Summing all numbers instead of only even
• Off-by-one error in loop
• Misunderstanding modulo operator

4. The following code attempts to solve the coin change problem using a greedy approach. What is the main issue?

int coinChange(int amount) {
    int coins[] = {25, 10, 5, 1};
    int count = 0;
    for (int i = 0; i < 4; i++) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            count++;
        }
    }
    return count;
}

medium

A. Greedy approach fails for some coin sets, not always optimal

B. The loop condition is incorrect and causes infinite loop

C. Coins array is not sorted in ascending order

D. The function does not return the count

Solution

1. Step 1: Understand greedy approach for coin change

   The greedy approach picks the largest coin repeatedly. It works only if coin denominations are canonical (like US coins).

2. Step 2: Identify problem with greedy for arbitrary coins

   For some coin sets, greedy does not give minimum coins. Dynamic programming is needed for guaranteed optimality.

3. Final Answer:

   Greedy approach fails for some coin sets, not always optimal -> Option A

4. Quick Check:

   Greedy coin change not always optimal [OK]

Hint: Greedy coin change fails if coins not canonical [OK]

Common Mistakes:

• Assuming greedy always gives minimum coins
• Ignoring coin set properties
• Confusing loop correctness with algorithm correctness

5. You have a set of tasks each with a deadline and profit. You want to schedule tasks to maximize profit without missing deadlines. Which approach is best and why?

struct Task {
    int deadline;
    int profit;
};

hard

A. Use greedy algorithm by sorting tasks by deadline only

B. Use dynamic programming to try all subsets of tasks and pick max profit

C. Use brute force to check all permutations of tasks

D. Use greedy algorithm by sorting tasks by profit and scheduling latest available slot

Solution

1. Step 1: Understand task scheduling problem

   This is a classic greedy problem where tasks are sorted by profit descending, then scheduled in the latest free slot before deadline.

2. Step 2: Compare approaches

   Dynamic programming or brute force is too slow. Sorting by deadline only does not maximize profit. Greedy by profit with latest slot is efficient and optimal.

3. Final Answer:

   Use greedy algorithm by sorting tasks by profit and scheduling latest available slot -> Option D

4. Quick Check:

   Greedy by profit + latest slot = max profit [OK]

Hint: Sort tasks by profit, schedule latest free slot [OK]

Common Mistakes:

• Sorting only by deadline misses max profit
• Trying DP or brute force unnecessarily
• Scheduling tasks without checking deadlines