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

DP vs Recursion vs Greedy: Choosing the Right Tool

📖 Scenario: You are helping a small delivery company decide the best way to calculate the minimum cost to deliver packages along a route. They want to understand three different approaches: simple recursion, greedy choice, and dynamic programming.This project will guide you through creating a simple problem and solving it with these three methods step-by-step.

🎯 Goal: Build a Java program that calculates the minimum delivery cost using recursion, greedy, and dynamic programming approaches. You will create the data, set up a cost limit, implement each method, and print the results to compare.

📋 What You'll Learn

Create an array of delivery costs for each stop

Set a maximum cost limit variable

Implement a recursive method to find minimum cost

Implement a greedy method to find minimum cost

Implement a dynamic programming method to find minimum cost

Print the results of all three methods

💡 Why This Matters

🌍 Real World

Delivery companies often need to calculate minimum costs for routes. Understanding different algorithm approaches helps choose the best method for efficiency and accuracy.

💼 Career

Knowing when to use recursion, greedy algorithms, or dynamic programming is essential for software engineers working on optimization problems, logistics, and resource management.

1

Create the delivery costs array

Create an integer array called deliveryCosts with these exact values: 5, 10, 3, 7, 2

DSA Java

// Create the deliveryCosts array with the given values
// Your code here

Hint

Use int[] deliveryCosts = {5, 10, 3, 7, 2}; to create the array.

2

Set the maximum cost limit

Create an integer variable called maxCost and set it to 15

DSA Java

int[] deliveryCosts = {5, 10, 3, 7, 2};
// Create maxCost variable and set it to 15
// Your code here

Hint

Use int maxCost = 15; to set the cost limit.

3

Implement recursive method to find minimum cost

Write a recursive method called minCostRecursive that takes the array deliveryCosts and an integer index and returns the minimum cost from index to the end. Use simple recursion without memoization.

DSA Java

int[] deliveryCosts = {5, 10, 3, 7, 2};
int maxCost = 15;

// Write minCostRecursive method here
// Your code here

Hint

Base case: if index reaches array length, return 0. Otherwise, add current cost and recurse for next index.

4

Print the minimum cost using recursion

Write a main method that calls minCostRecursive with deliveryCosts and 0 as arguments, then prints the result with System.out.println.

DSA Java

int[] deliveryCosts = {5, 10, 3, 7, 2};
int maxCost = 15;

public static int minCostRecursive(int[] deliveryCosts, int index) {
    if (index == deliveryCosts.length) {
        return 0;
    }
    int costWithCurrent = deliveryCosts[index] + minCostRecursive(deliveryCosts, index + 1);
    return costWithCurrent;
}

// Write main method to call minCostRecursive and print result
// Your code here

Hint

Call minCostRecursive(deliveryCosts, 0) and print the result.

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

D. Brute Force

Solution

1. Step 1: Understand problem properties

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

2. Step 2: Match approach to properties

   Dynamic Programming stores results of subproblems to avoid repeated work, ideal for these properties.

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 memoization
• Confusing optimal substructure with greedy choice property

2. Which of the following Java method signatures correctly represents a recursive function to compute factorial?

easy

A. public static int factorial(int n) { if (n == 1) return 0; else return n + factorial(n - 1); }

B. public static int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); }

C. public static int factorial(int n) { for (int i = 1; i <= n; i++) return i; }

D. public static int factorial(int n) { while (n > 0) n = n - 1; return n; }

Solution

1. Step 1: Check base case correctness

   Factorial base case is 0! = 1, so if (n == 0) return 1 is correct.

2. Step 2: Check recursive call and calculation

   Factorial(n) = n * factorial(n-1) is correct recursive formula.

3. Final Answer:

   public static int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } -> Option B

4. Quick Check:

   Correct base case and recursive multiplication = public static int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } [OK]

Hint: Factorial recursion multiplies n by factorial(n-1) with base n=0 [OK]

Common Mistakes:

• Wrong base case (e.g., returning 0 instead of 1)
• Using loops instead of recursion
• Returning addition instead of multiplication

3. What will be the output of the following Java code snippet?

public class Test {
  public static int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
  }
  public static void main(String[] args) {
    System.out.println(fib(4));
  }
}

medium

A. 3

B. 5

C. 4

D. 7

Solution

1. Step 1: Trace fib(4) calls

   fib(4) = fib(3) + fib(2). fib(3) = fib(2) + fib(1), fib(2) = fib(1) + fib(0).

2. Step 2: Calculate values bottom-up

   fib(0)=0, fib(1)=1, so fib(2)=1+0=1, fib(3)=1+1=2, fib(4)=2+1=3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Fibonacci(4) = 3 [OK]

Hint: Fibonacci(4) = 3 by adding previous two Fibonacci numbers [OK]

Common Mistakes:

• Confusing index starting at 0 or 1
• Adding wrong recursive results
• Assuming fib(4) = 5 (fibonacci(5))

4. Identify the error in this greedy algorithm code snippet for coin change problem:

public static int minCoins(int[] coins, int amount) {
  int count = 0;
  for (int coin : coins) {
    while (amount >= coin) {
      amount -= coin;
      count++;
    }
  }
  return count;
}

medium

A. Missing base case for amount = 0

B. Should use recursion instead of loops

C. Coins array must be sorted in descending order

D. Count variable should be reset inside the loop

Solution

1. Step 1: Understand greedy coin change logic

   Greedy picks largest coin first to minimize count. Coins must be sorted descending for this to work.

2. Step 2: Check code for sorting

   Code does not sort coins, so if coins are unsorted, greedy picks smaller coins first, leading to wrong answer.

3. Final Answer:

   Coins array must be sorted in descending order -> Option C

4. Quick Check:

   Greedy coin change needs descending sorted coins [OK]

Hint: Sort coins descending for greedy coin change to work correctly [OK]

Common Mistakes:

• Not sorting coins before greedy selection
• Using recursion unnecessarily
• Resetting count inside loop causing wrong count

5. You want to find the minimum number of jumps to reach the end of an array where each element represents max jump length at that position. Which approach is best and why?

int[] arr = {2,3,1,1,4};

hard

A. Use Dynamic Programming to store minimum jumps for each index

B. Use simple recursion to try all jump combinations

C. Use Brute Force to check every path

D. Use Greedy approach to jump to the farthest reachable index

Solution

1. Step 1: Analyze problem nature

   Minimum jumps problem can be solved efficiently by greedy because at each step, jumping to the farthest reachable index reduces total jumps.

2. Step 2: Compare approaches

   Recursion or DP works but are slower. Greedy gives optimal solution in linear time for this problem.

3. Final Answer:

   Use Greedy approach to jump to the farthest reachable index -> Option D

4. Quick Check:

   Minimum jumps = Greedy farthest jump [OK]

Hint: Jump farthest reachable index greedily for minimum jumps [OK]

Common Mistakes:

• Using recursion causing timeouts
• Overcomplicating with DP when greedy suffices
• Ignoring problem constraints for greedy validity