Toph's Earthbending Training - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 20 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 minimize the total energy required for Toph to reach the top of the staircase.
• Can Toph start at any point other than index 0 or 1?
  • No, Toph can only start at either step 0 or step 1.
• Does she have to reach exactly the top step, or can she go beyond?
  • Toph must reach the top step, and the minimum energy required to reach the top is calculated.

HAPPY CASE
Input: 
    cost = [10, 15, 20]
Output: 
    15
Explanation:
    Toph will start at index 1, pay 15 units of energy, and jump two steps to the top. Total energy: 15.

EDGE CASE
Input: 
    cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 
    6
Explanation:
    Toph will minimize energy by taking steps in a pattern that uses the least energy, resulting in a total energy cost of 6.

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 minimizing energy problems, we want to consider the following approaches:

• Dynamic Programming (DP): At each step, Toph can either jump one step or two steps, and we need to calculate the minimum energy required to reach each step.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use dynamic programming to compute the minimum energy required to reach the top of the staircase. Toph can start at either the first or second step, and for each step, she can choose to take one or two steps forward, aiming to minimize her energy expenditure.

Steps:

1. Base Case:

   • If the number of steps is less than 2, return the minimum of cost[0] or cost[1].

2. Dynamic Programming Array:

   • Create a DP array dp where dp[i] stores the minimum energy required to reach step i.

3. Recurrence Relation:

   • For each step i from step 2 onwards, calculate dp[i] as the minimum of dp[i - 1] and dp[i - 2], plus the energy cost at step i.

4. Return the Result:

   • The final answer is the minimum energy required to reach the top step, which is the minimum of the last two entries in the DP array (dp[n-1] and dp[n-2]).

4: I-mplement

Implement the code to solve the algorithm.

def toph_training(cost):
    n = len(cost)
    
    # If there is only one step, return the cost of that step
    if n == 1:
        return cost[0]
    
    # Create a dp array to store the minimum energy to reach each step
    dp = [0] * n
    
    # Base cases: minimum energy required to reach the first or second step
    dp[0] = cost[0]
    dp[1] = cost[1]
    
    # Fill the dp array for the rest of the steps
    for i in range(2, n):
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
    
    # Return the minimum energy to reach the top, which could be the last or second last step
    return min(dp[n - 1], dp[n - 2])

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: cost = [10, 15, 20]
• Expected Output: 15

Example 2:

• Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
• Expected Output: 6

6: E-valuate

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

Assume n is the number of steps in the staircase.

• Time Complexity: O(n) because we calculate the minimum energy for each step.
• Space Complexity: O(n) to store the DP array.