Greedy vs DP How to Know Which to Apply in DSA C++ - Trade-offs & Analysis

Mental Model

Greedy makes the best choice now, hoping it leads to the best overall. DP tries all choices and remembers results to find the best overall.

Analogy: Choosing snacks: greedy is like picking the tastiest snack first without thinking ahead; DP is like planning all snacks to get the tastiest total meal.

Choices: [1] -> [2] -> [3] -> [4]
Greedy picks step by step ->
DP explores all paths and remembers best results

Dry Run Walkthrough

Input: Problem: Maximize sum by picking numbers from list [1, 2, 9, 4, 5, 0, 4, 11, 6] without picking adjacent numbers

Goal: Decide if greedy or DP works better and find max sum

Step 1: Greedy picks 1 (first number)

Picked: 1, Remaining: 2 -> 9 -> 4 -> 5 -> 0 -> 4 -> 11 -> 6

Why: Greedy picks best immediate number

Step 2: Greedy skips 2 (adjacent to 1), picks 9

Picked: 1, 9, Remaining: 4 -> 5 -> 0 -> 4 -> 11 -> 6

Why: Greedy picks next best number ignoring future impact

Step 3: Greedy skips 4 (adjacent to 9), picks 5

Picked: 1, 9, 5, Remaining: 0 -> 4 -> 11 -> 6

Why: Greedy continues picking local best

Step 4: Greedy skips 0 (adjacent to 5), picks 4

Picked: 1, 9, 5, 4, Remaining: 11 -> 6

Why: Greedy picks next best ignoring future

Step 5: Greedy skips 11 (adjacent to 4), picks 6

Picked: 1, 9, 5, 4, 6

Why: Greedy picks last number

Step 6: Sum of greedy picks = 1 + 9 + 5 + 4 + 6 = 25

Final sum = 25

Why: Greedy total sum

Step 7: DP tries all combinations remembering max sums: Index 0: max = 1 Index 1: max = max(1,2) = 2 Index 2: max = max(2, 1+9) = 10 Index 3: max = max(10, 2+4) = 10 Index 4: max = max(10, 10+5) = 15 Index 5: max = max(15, 10+0) = 15 Index 6: max = max(15, 15+4) = 19 Index 7: max = max(19, 15+11) = 26 Index 8: max = max(26, 19+6) = 26

DP max sum = 26

Why: DP finds better total by exploring all options

Result:

Greedy picks sum 25 but DP finds max sum 26
DP is better here because greedy misses better combinations

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Function to find max sum without adjacent picks using DP
int maxSumNoAdjacent(const vector<int>& nums) {
    if (nums.empty()) return 0;
    if (nums.size() == 1) return nums[0];

    vector<int> dp(nums.size(), 0);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);

    for (size_t i = 2; i < nums.size(); ++i) {
        dp[i] = max(dp[i-1], dp[i-2] + nums[i]); // choose max between skipping or picking current
    }
    return dp.back();
}

// Greedy approach: pick number if it's not adjacent to previously picked
int greedySum(const vector<int>& nums) {
    int sum = 0;
    int prevPickedIndex = -2; // to track adjacency
    for (size_t i = 0; i < nums.size(); ++i) {
        if (i - prevPickedIndex > 1) { // not adjacent
            sum += nums[i];
            prevPickedIndex = i;
        }
    }
    return sum;
}

int main() {
    vector<int> nums = {1, 2, 9, 4, 5, 0, 4, 11, 6};

    int greedy_result = greedySum(nums);
    int dp_result = maxSumNoAdjacent(nums);

    cout << "Greedy sum: " << greedy_result << "\n";
    cout << "DP max sum: " << dp_result << "\n";

    return 0;
}

dp[i] = max(dp[i-1], dp[i-2] + nums[i]); // choose max between skipping or picking current

choose best sum by either skipping current or picking it plus best two steps before

if (i - prevPickedIndex > 1) { sum += nums[i]; prevPickedIndex = i; }

greedy picks current if not adjacent to last picked

Output

Greedy sum: 25

DP max sum: 26

Complexity Analysis

Time: O(n) because we scan the list once for DP and once for greedy

Space: O(n) for DP due to storing max sums, O(1) for greedy as it uses simple variables

vs Alternative: DP is more thorough and finds optimal solution but uses more space; greedy is faster and simpler but can miss better solutions

Edge Cases

Empty list

Both DP and greedy return 0 safely

DSA C++

if (nums.empty()) return 0;

Single element list

Both return that single element as max sum

DSA C++

if (nums.size() == 1) return nums[0];

All elements equal

DP and greedy may pick different sums; DP guarantees max

DSA C++

dp[i] = max(dp[i-1], dp[i-2] + nums[i]);

When to Use This Pattern

When a problem asks for an optimal solution with overlapping subproblems and choices, consider DP; if local best choices seem to lead to global best without backtracking, greedy might work.

Common Mistakes

Mistake: Assuming greedy always works without checking problem constraints
Fix: Test greedy on examples and verify if it finds optimal; if not, use DP

Mistake: Not handling adjacency or overlapping subproblems properly in DP
Fix: Use dp array to store best results up to each index considering constraints

Summary

Greedy picks the best immediate choice, DP explores all choices and remembers results.

Use greedy when local choices lead to global optimum; use DP when choices overlap and future depends on past.

The key insight is to check if problem has overlapping subproblems and optimal substructure to decide DP over greedy.

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