Greedy vs DP How to Know Which to Apply in DSA C++ - Key Differences

Recall & Review

beginner

What is the main idea behind the greedy approach?

The greedy approach makes the best choice at each step, hoping to find the overall best solution without reconsidering previous choices.

beginner

What does Dynamic Programming (DP) do differently compared to greedy?

DP solves problems by breaking them into smaller overlapping subproblems, solving each once, and storing results to avoid repeated work.

intermediate

When should you choose a greedy algorithm over DP?

Choose greedy when the problem has the greedy-choice property and optimal substructure, meaning local best choices lead to a global best solution.

beginner

What is the 'optimal substructure' property?

A problem has optimal substructure if an optimal solution can be built from optimal solutions of its subproblems.

intermediate

How can you test if a greedy approach works for a problem?

Try to prove that making local optimal choices leads to a global optimum, or test with examples to see if greedy fails compared to DP.

Which property must a problem have for a greedy algorithm to work correctly?

A Greedy-choice property

B Overlapping subproblems

C Memoization

D Backtracking

The greedy-choice property means local optimal choices lead to a global optimum, which is essential for greedy algorithms.

Dynamic Programming is best used when a problem has:

A Greedy-choice property only

B Overlapping subproblems and optimal substructure

C No subproblems

D Only one solution

DP works well when problems have overlapping subproblems and optimal substructure.

Which approach stores results of subproblems to avoid repeated work?

A Dynamic Programming

B Greedy

C Brute Force

D Divide and Conquer

Dynamic Programming stores results (memoization or tabulation) to avoid recomputing subproblems.

If a greedy algorithm fails on some inputs, what should you try next?

A Use brute force

B Use sorting only

C Use dynamic programming

D Use recursion without memoization

If greedy fails, DP often works because it explores all subproblems systematically.

Which of these is NOT a characteristic of greedy algorithms?

A Fast and simple

B Make local optimal choices

C Do not reconsider choices

D Use memoization

Greedy algorithms do not use memoization; that is a feature of dynamic programming.

Explain how to decide between using a greedy algorithm or dynamic programming for a problem.

Think about problem properties and how solutions build from subproblems.

Describe the main differences in approach between greedy algorithms and dynamic programming.

Focus on how each method handles choices and subproblems.

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