DP vs Recursion vs Greedy Choosing the Right Tool in DSA C++ - Trade-offs & Analysis

Mental Model

We have three ways to solve problems: recursion tries all options, greedy picks the best now, and dynamic programming remembers past results to avoid repeats.

Analogy: Imagine climbing stairs: recursion tries every path, greedy picks the next step that looks easiest, and dynamic programming remembers which steps cost less to avoid redoing work.

Recursion tree:
    root
   /    \
  /      \
left    right

Greedy path:
start -> best next -> best next -> end

DP table:
index: 0 1 2 3
value: x y z w
memo:  - - - -

Dry Run Walkthrough

Input: Find minimum cost to climb stairs with costs [10, 15, 20]

Goal: Show how recursion, greedy, and DP solve the same problem differently

Step 1: Recursion tries climbing from step 0 and step 1 separately

Recursion tree:
start
├─ step0 (cost 10)
└─ step1 (cost 15)

Why: We explore all possible starting points to find minimum cost

Step 2: Recursion explores step 0 path: step0 -> step2 (cost 20)

Recursion tree:
start
├─ step0 (10)
│  └─ step2 (20)
└─ step1 (15)

Why: We try all paths to the top by jumping 1 or 2 steps

Step 3: Greedy picks step 0 (10) then step 1 (15) because 15 < 20

Greedy path:
start -> step0 (10) -> step1 (15) -> end

Why: Greedy chooses the cheaper immediate step without looking ahead

Step 4: DP stores minimum cost to reach each step to avoid repeated work

DP table:
index: 0  1  2
cost: 10 15 20
min:  10 15 35

Why: DP remembers results to avoid recalculating costs for same steps

Step 5: DP finds minimum cost to reach top is min(min[1], min[2]) = min(15, 35) = 15

DP final:
min cost to top = 15

Why: DP combines stored results to find overall minimum cost

Result:

Minimum cost to climb stairs is 15

Annotated Code

DSA C++

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

// Recursive solution: tries all paths
int minCostRec(const vector<int>& cost, int step) {
    if (step >= cost.size()) return 0; // reached top
    // try stepping 1 or 2 steps ahead
    int oneStep = minCostRec(cost, step + 1);
    int twoStep = minCostRec(cost, step + 2);
    return cost[step] + min(oneStep, twoStep);
}

// Greedy solution: picks cheaper next step
int minCostGreedy(const vector<int>& cost) {
    int total = 0;
    int i = 0;
    while (i < cost.size()) {
        total += cost[i];
        if (i + 2 < cost.size() && cost[i + 1] > cost[i + 2]) {
            i += 2; // jump two steps if cheaper
        } else {
            i += 1; // else jump one step
        }
    }
    return total;
}

// DP solution: stores minimum cost to reach each step
int minCostDP(const vector<int>& cost) {
    int n = cost.size();
    vector<int> dp(n + 1, 0); // dp[i] = min cost to reach step i
    dp[0] = 0; // start before first step
    dp[1] = cost[0]; // cost to step 0
    for (int i = 2; i <= n; i++) {
        dp[i] = cost[i - 1] + min(dp[i - 1], dp[i - 2]);
    }
    return dp[n];
}

int main() {
    vector<int> cost = {10, 15, 20};
    cout << "Recursion min cost: " << minCostRec(cost, 0) << "\n";
    cout << "Greedy min cost: " << minCostGreedy(cost) << "\n";
    cout << "DP min cost: " << minCostDP(cost) << "\n";
    return 0;
}

int minCostRec(const vector<int>& cost, int step) {

start recursion from current step

if (step >= cost.size()) return 0;

base case: reached top, no cost

int oneStep = minCostRec(cost, step + 1);

recurse stepping 1 ahead

int twoStep = minCostRec(cost, step + 2);

recurse stepping 2 ahead

return cost[step] + min(oneStep, twoStep);

choose cheaper path and add current cost

while (i < cost.size()) {

iterate steps greedily

if (i + 2 < cost.size() && cost[i + 1] > cost[i + 2]) {

choose jump of 2 if next step cost higher than step after

dp[i] = cost[i - 1] + min(dp[i - 1], dp[i - 2]);

dp stores min cost to reach step i using previous results

Output

Recursion min cost: 35

Greedy min cost: 25

DP min cost: 35

Complexity Analysis

Time: Recursion: O(2^n) because it tries all paths; Greedy: O(n) because it scans once; DP: O(n) because it fills table once

Space: Recursion: O(n) due to call stack; Greedy: O(1) constant space; DP: O(n) for dp table

vs Alternative: DP improves over recursion by storing results to avoid repeated work; Greedy is faster but may give wrong answer if problem requires global view

Edge Cases

Empty cost array

All methods return 0 cost as no steps to climb

DSA C++

if (step >= cost.size()) return 0;

Single step cost array

Methods return cost of that single step

DSA C++

dp[1] = cost[0];

Costs where greedy fails (e.g., cost = [1, 100, 1])

Greedy picks expensive step, recursion and DP find cheaper path

DSA C++

if (i + 2 < cost.size() && cost[i + 1] > cost[i + 2]) {

When to Use This Pattern

When a problem asks for optimal cost or count with overlapping subproblems, consider DP; if problem can be solved by making local best choices, try greedy; if problem is small or simple, recursion can work but may be slow.

Common Mistakes

Mistake: Using greedy when problem requires global optimal solution
Fix: Use DP or recursion to explore all options or store results

Mistake: Not storing results in recursion causing repeated work
Fix: Add memoization or switch to DP

Summary

Recursion tries all options, greedy picks local best, and DP remembers past results to avoid repeats.

Use recursion for simple or small problems, greedy when local choices lead to global optimum, and DP when subproblems overlap and global optimum is needed.

The key is to recognize if the problem has overlapping subproblems and optimal substructure to choose DP, or if greedy choices are safe.

Practice

1. Which approach is best suited when a problem has overlapping subproblems and optimal substructure?

easy

A. Dynamic Programming

B. Greedy Algorithm

C. Simple Recursion without memoization

D. Brute Force

Solution

1. Step 1: Understand problem characteristics

   Overlapping subproblems means the same smaller problems repeat. Optimal substructure means the best solution can be built from best solutions of smaller problems.

2. Step 2: Match approach to characteristics

   Dynamic Programming stores results of subproblems to avoid recomputation, ideal for overlapping subproblems and optimal substructure.

3. Final Answer:

   Dynamic Programming -> Option A

4. Quick Check:

   Overlapping subproblems + optimal substructure = Dynamic Programming [OK]

Hint: Use DP when subproblems repeat and build optimal solutions [OK]

Common Mistakes:

• Choosing greedy when subproblems overlap
• Using simple recursion without memo causing slow code
• Confusing optimal substructure with greedy choice property

2. Which of the following is the correct syntax to implement memoization in C++ recursion?

easy

A. Use a while loop instead of recursion

B. Use a for loop inside the recursive function

C. Call the recursive function twice without storing results

D. Use a global array or vector to store results and check before recursion

Solution

1. Step 1: Understand memoization concept

   Memoization stores results of recursive calls to avoid repeated work.

2. Step 2: Identify correct syntax usage

   Using a global or passed array/vector to save results and checking it before recursion is the correct way.

3. Final Answer:

   Use a global array or vector to store results and check before recursion -> Option D

4. Quick Check:

   Memoization = store results before recursion [OK]

Hint: Memoize by storing results in array before recursive calls [OK]

Common Mistakes:

• Not storing results causing repeated calculations
• Using loops inside recursion incorrectly
• Calling recursion multiple times without memo

3. What is the output of the following C++ code snippet?

int fib(int n) {
  if (n <= 1) return n;
  return fib(n-1) + fib(n-2);
}

int main() {
  std::cout << fib(4);
  return 0;
}

medium

A. 4

B. 5

C. 3

D. 7

Solution

1. Step 1: Trace fib(4) calls

   fib(4) = fib(3) + fib(2) - fib(3) = fib(2) + fib(1) = (fib(1)+fib(0)) + 1 = (1+0)+1=2 - fib(2) = fib(1) + fib(0) = 1 + 0 = 1 So fib(4) = 2 + 1 = 3

2. Step 2: Confirm output

   The program prints 3 as the result of fib(4).

3. Final Answer:

   3 -> Option C

4. Quick Check:

   fib(4) = 3 [OK]

Hint: Trace small inputs stepwise to find Fibonacci output [OK]

Common Mistakes:

• Confusing fib(4) with fib(5)
• Adding wrong Fibonacci numbers
• Assuming fib(4) equals 4

4. Identify the error in the following code snippet implementing a greedy approach for coin change:

int coinChange(int amount, vector<int>& coins) {
  int count = 0;
  for (int i = 0; i < coins.size(); i++) {
    while (amount >= coins[i]) {
      amount -= coins[i];
      count++;
    }
  }
  return count;
}

medium

A. Coins vector is not sorted in descending order

B. Using while loop inside for loop is incorrect

C. Function should return amount, not count

D. No error, code is correct

Solution

1. Step 1: Analyze greedy coin change logic

   Greedy coin change requires coins sorted descending to pick largest coin first.

2. Step 2: Identify error in code

   The code loops coins in given order; if coins are not sorted descending, greedy fails to minimize count.

3. Final Answer:

   Coins vector is not sorted in descending order -> Option A

4. Quick Check:

   Greedy coin change needs descending sorted coins [OK]

Hint: Sort coins descending before greedy coin change [OK]

Common Mistakes:

• Not sorting coins descending
• Returning wrong variable
• Thinking while loop inside for is wrong

5. You want to find the minimum number of coins to make a given amount using coins of denominations [1, 3, 4]. Which approach is best and why?

hard

A. Greedy approach because picking largest coin first always works

B. Dynamic Programming to store minimum coins needed for sub-amounts

C. Simple recursion without memoization to try all combinations

D. Brute force by checking all subsets of coins

Solution

1. Step 1: Understand problem requirements

   We want minimum coins for amount using coins [1,3,4]. Greedy fails here because picking largest coin first may not give minimum coins.

2. Step 2: Choose best approach

   Dynamic Programming stores minimum coins for all smaller amounts, building up to the target efficiently and correctly.

3. Final Answer:

   Dynamic Programming to store minimum coins needed for sub-amounts -> Option B

4. Quick Check:

   Minimum coins with tricky denominations = DP [OK]

Hint: Use DP when greedy fails to find minimum coins [OK]

Common Mistakes:

• Assuming greedy always works for coin change
• Using recursion without memo causing slow code
• Trying brute force which is inefficient