DP vs Recursion vs Greedy Choosing the Right Tool in DSA C++ - Build Both Approaches

DP vs Recursion vs Greedy: Choosing the Right Tool

📖 Scenario: Imagine you are organizing a small event and need to decide how to allocate your budget to buy snacks. You have a list of snack options with their costs and tastiness scores. You want to maximize tastiness without exceeding your budget.

🎯 Goal: You will create a program that helps decide which snacks to buy using three different approaches: recursion, dynamic programming, and greedy. This will help you understand when each method works best.

📋 What You'll Learn

Create a list of snack costs and tastiness scores

Set a budget limit

Implement a recursive function to find the best tastiness within budget

Implement a dynamic programming solution for the same problem

Implement a greedy approach based on tastiness-to-cost ratio

Print the maximum tastiness found by each method

💡 Why This Matters

🌍 Real World

Budgeting and resource allocation problems where you want to maximize value under constraints.

💼 Career

Understanding these approaches helps in software roles involving optimization, planning, and algorithm design.

1

Create snack data and budget

Create a vector of integers called costs with values {2, 3, 4, 5} and a vector of integers called tastiness with values {3, 4, 5, 6}. Also create an integer variable called budget and set it to 8.

DSA C++

// Your code here

Hint

Use vector<int> to store costs and tastiness. Set budget as an int.

2

Add recursive function to find max tastiness

Add a recursive function called maxTastinessRecursive that takes three parameters: int index, int remainingBudget, and returns an int. It should return 0 if index is equal to the size of costs. Otherwise, it should return the maximum tastiness by either skipping the current snack or buying it if the cost fits in remainingBudget.

DSA C++

#include 
#include 
using namespace std;

vector costs = {2, 3, 4, 5};
vector tastiness = {3, 4, 5, 6};
int budget = 8;

// Add recursive function maxTastinessRecursive here

Hint

Use recursion to explore both choices: skip or take the snack if budget allows.

3

Add dynamic programming solution

Add a function called maxTastinessDP that uses a 2D vector dp of size (costs.size() + 1) x (budget + 1) to store maximum tastiness values. Fill dp bottom-up and return the maximum tastiness for all snacks and full budget.

DSA C++

#include 
#include 
using namespace std;

vector costs = {2, 3, 4, 5};
vector tastiness = {3, 4, 5, 6};
int budget = 8;

int maxTastinessRecursive(int index, int remainingBudget) {
    if (index == (int)costs.size()) {
        return 0;
    }
    int skip = maxTastinessRecursive(index + 1, remainingBudget);
    int take = 0;
    if (costs[index] <= remainingBudget) {
        take = tastiness[index] + maxTastinessRecursive(index + 1, remainingBudget - costs[index]);
    }
    return max(skip, take);
}

// Add maxTastinessDP function here

Hint

Use a 2D vector to store results for each snack index and budget. Fill it from the bottom up.

4

Add greedy approach and print results

Add a function called maxTastinessGreedy that creates a vector of pairs of double ratio (tastiness/cost) and index. Sort it in descending order by ratio. Then pick snacks in this order while budget allows, summing tastiness. Finally, print the results of maxTastinessRecursive(0, budget), maxTastinessDP(), and maxTastinessGreedy() each on its own line.

DSA C++

#include 
#include 
#include 
using namespace std;

vector costs = {2, 3, 4, 5};
vector tastiness = {3, 4, 5, 6};
int budget = 8;

int maxTastinessRecursive(int index, int remainingBudget) {
    if (index == (int)costs.size()) {
        return 0;
    }
    int skip = maxTastinessRecursive(index + 1, remainingBudget);
    int take = 0;
    if (costs[index] > dp(n + 1, vector(budget + 1, 0));
    for (int i = n - 1; i >= 0; i--) {
        for (int b = 0; b <= budget; b++) {
            int skip = dp[i + 1][b];
            int take = 0;
            if (costs[i] <= b) {
                take = tastiness[i] + dp[i + 1][b - costs[i]];
            }
            dp[i][b] = max(skip, take);
        }
    }
    return dp[0][budget];
}

// Add maxTastinessGreedy function and print statements here

Hint

Sort snacks by tastiness-to-cost ratio and pick as many as budget allows. Then print results of all three methods.

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