Team Rocket's Heist Plan - codepath/compsci_guides GitHub Wiki

Unit 12 Session 1 Standard (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 15 mins
  • 🛠️ Topics: Dynamic Programming

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

  • What is the goal of the problem?

    • The goal is to calculate the maximum number of Pokéballs Team Rocket can steal without robbing adjacent Pokémon Centers.

  • Can Team Rocket rob the first and last centers?

    • Yes, as long as they aren't adjacent.

  • How is the problem structured?

    • The problem is structured like a variation of the ""house robbery"" problem, where we cannot rob adjacent locations.
HAPPY CASE
Input: 
    pokeballs = [1, 2, 3, 1]
Output: 
    4
Explanation:
    Team Rocket should rob Pokémon Center 1 (1 Pokéball) and Pokémon Center 3 (3 Pokéballs).
    Total = 1 + 3 = 4.

EDGE CASE
Input: 
    pokeballs = [2, 7, 9, 3, 1]
Output: 
    12
Explanation:
    The optimal plan is to rob Pokémon Centers 1, 3, and 5.
    Total = 2 + 9 + 1 = 12.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For robbery problems where adjacent options are constrained, we want to consider the following approaches:

  • Dynamic Programming (DP): This is the best approach as we can keep track of the maximum profit so far, either robbing or skipping the current Pokémon Center.
  • Greedy Approach: Might not work because we can't guarantee it will give the best outcome for non-adjacent centers.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use dynamic programming to compute the maximum number of Pokéballs Team Rocket can steal, keeping track of two possible choices: either rob the current center or skip it. We'll fill a DP table where each entry dp[i] stores the maximum number of Pokéballs that can be stolen up to the i-th center.

Steps:

  1. Base Case:

    • If there are no Pokémon Centers, return 0.
    • If there's only one center, return the Pokéballs in that center.

  2. Dynamic Programming Array:

    • Initialize a DP array dp of size n to store the maximum Pokéballs stolen up to each center.
    • Set dp[0] to pokeballs[0] and dp[1] to max(pokeballs[0], pokeballs[1]).

  3. Recurrence Relation:

    • For each center i starting from 2, set dp[i] = max(dp[i - 1], dp[i - 2] + pokeballs[i]).
    • This formula means we either skip robbing the current center (and use the value from dp[i - 1]), or rob it and add its value to the total we had two centers before (dp[i - 2]).

  4. Return the Result:

    • Return the value in dp[n-1], which gives the maximum Pokéballs Team Rocket can steal.

4: I-mplement

Implement the code to solve the algorithm.

def heist_plan(pokeballs):
    if not pokeballs:
        return 0
    
    n = len(pokeballs)
    if n == 1:
        return pokeballs[0]
    
    # Initialize the dp array
    dp = [0] * n
    dp[0] = pokeballs[0]
    dp[1] = max(pokeballs[0], pokeballs[1])
    
    # Fill dp array using the recurrence relation
    for i in range(2, n):
        dp[i] = max(dp[i - 1], dp[i - 2] + pokeballs[i])
    
    return dp[-1]

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Example 1:

  • Input: pokeballs = [1, 2, 3, 1]
  • Expected Output: 4

Example 2:

  • Input: pokeballs = [2, 7, 9, 3, 1]
  • Expected Output: 12

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume n is the length of the input array.

  • Time Complexity: O(n) since we iterate through the list once.
  • Space Complexity: O(n) to store the DP array.