51 weeks to go

746. Min Cost Climbing Stairs

In partnership with

Drowning In Support Tickets? Maven AGI is here to help.

Maven AGI platform simplifies customer service by unifying systems, improving with every interaction, and automating up to 93% of responses. Seamlessly integrated with 50+ tools like Salesforce, Freshdesk, and Zendesk, Maven can deploy AI agents across multiple channels—text, email, web, voice, and apps—within days. Companies like Tripadvisor, ClickUp, and Rho slash response times by 60%, ensuring quicker support and exceptional customer satisfaction. Don’t let support tickets slow you down

TLDR

  1. Welcome!

  2. 746. Min Cost Climbing Stairs

  3. Recommendations I live by!

  4. Resources to check out  

  5. Let me invoke you into my cult

  6. JOBS & SCHOLARSHIPS

Hi and welcome back, brave human!

Happy New Year!! I am so glad we are back!!!!!

What are your plans for 2025 besides getting damn good at LeetCode? Write them in the comments!

For me, this year is the year of curing my leaky brain.

Denisse but wtf is a leaky brain?

A leaky brain is when I start a task and think and do everything but the task I need to complete.

Just to give you an insight, every time I need to LeetCode, my apartment ends up clean.

Coincidence? I don’t think so.

My plan to cure my leaky brain is to send me calendar invites with the task I need to do in hand and the description of what I need to accomplish during that period of time.

Have a better idea? Let me know! Reply to this email with the suggestions…

LeetCode problem

Given cost, where each value is the step cost, climb one or two steps. 

Return the minimum cost to reach or pass the top.

Before we get started let's take a deep breathThis is a warm-up exercise for the year to come!!!

It took me some good time to wrap my head around this problem, so let’s take it step by step!

  • What are we asked? Find the minimum cost of climbing the stairs.

  • What do we need to calculate each step? For each step, we need to check what is cheaper if giving one or two jumps.

  • Base cases: dp[0] = cost[0] dp[1] = cost[1] 

Let's look at an example with [10,15,20].

The sequence builds up like this:

  1. dp[0] = 10

  2. dp[1] = 15

  3. dp[2] = cost[2] + min(dp[0], dp[1]) = 20 + min(10, 15) = 20 + 10 = 30

There is a third case that will be the top of the stairs. The cost of getting to the top is the minimum of the previous two steps, with no additional cost.

  • min(dp[1], dp[2]) = min(15, 30) = 15

So for [10,15,20], the answer is 15 because we only need one step

We will use dynamic programming to solve this problem. This problem is a combination of coin change and climbing stairs.

Top-Down Approach

There's a very basic template for most top-down recursive approaches!

  1. Base case: Define when to stop recursion (at the smallest subproblems)!

  2. Memoization: If computation was previously done and stored, just retrieve it!

  3. Formula: If computation wasn't done before, compute and save the result!

Let's use the template for this problem:

  1. Base case: Since we can start in either step 1 or 2 our base cases are:

    • dp[0] = cost[0] 

    • dp[1] = cost[1]

  2. Memoization: We'll use the array dp to store the minimum cost for each stair.

  3. Formula for each step: dp[n] = cost[n] + min(dp[n - 1], dp[n - 2]) . The cost to reach each step is the cost of the step + the cheapest 💰️ of the previous two steps.

  4. Formula for the top of the stairs: Since we are already at the top 💅 , we don’t need to pay the cost of being there. So the cost of reaching the last step is:

    dp[n] = min(dp[n - 1], dp[n - 2])

    For example: [1, 20, 15, 10] :

    Min Cost Cimbing Stairs: Top Down Approach

class Solution {
public:
    
    int auxMinCostClimbingStars(vector<int> cost, vector<int>& dp, int n){
        if (n == 0) {
            return cost[0];
        }
        if (n == 1) {
            return cost[1];
        }
         if(dp[n]!=-1){
            return dp[n]; 
        }
       
        if(n==cost.size()){
            dp[n] = min(auxMinCostClimbingStars(cost, dp, n-1), auxMinCostClimbingStars(cost, dp, n-2) );
        }
        if(dp[n]==-1){
            dp[n] = cost[n] + 
            min(auxMinCostClimbingStars(cost, dp, n-1), auxMinCostClimbingStars(cost, dp, n-2) );
        }
        
        
        return dp[n]; 
         
    }
    
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int>dp(cost.size()+1, -1); 
        int n= cost.size(); 
        return auxMinCostClimbingStars(cost, dp, n); 

     
    }
};

Bottom-Up Approach

The only difference is we will build iteratively from the base cases to bigger problems until we have solved our main problem! So we start by solving our base cases, and up from there! We start by initializing an array dp where dp[i] represents the minimum cost to reach the ith step We'll set dp[0] = cost[0] and dp[1] = cost[1] as our base cases (since these are the costs to start at first two steps).

Then comes the fun part 🥳 , building the array back up. We solve this one step at a time, from 2 up to our target n. For each step i:

  1. We consider both ways to get to step i (either from i-1 or i-2)

  2. For each way, we add the current step's cost to the previous min cost

  3. Keep track of the minimum result found To keep track of the minimum result found, we will:

  • dp[i] - current best (minimum) cost to reach step i

  • dp[i-1] - minimum cost if we came from previous step

  • dp[i-2] - minimum cost if we came from two steps back

  • cost[i] - cost of the current step we're on

  • + cost[i] - adds cost of using current step

  • min(dp[i-1] + cost[i], dp[i-2] + cost[i]) - keeps the minimum between coming from one or two steps back

This gives us our final DP transition: dp[i] = cost[i] + min(dp[i-1], dp[i-2])

Since we can reach the top from either the last or second-to-last step, our final answer is min(dp[n-1], dp[n-2])!

int minCostClimbingStairs(vector<int>& cost) {
        vector<int>dp(cost.size()+1, 0); 
        dp[0]=cost[0];
        dp[1]=cost[1];    
        for (int x = 2; x <= cost.size(); x++) {
        if (x != cost.size()) {
            dp[x] = cost[x] + min(dp[x-1], dp[x-2]);
        } else {
            dp[x] = min(dp[x-1], dp[x-2]); // No additional cost for climbing past the last step
        }
       }

     return dp[cost.size()];
    }
};

Recommendations

Level up your inbox by subscribing to what I am subscribed to!

Let me invoke you into my cult

Media worth seeing

  1. "You don't need to be aggressive to be at the top" - Roger Federer. During the holidays I binged RF new documentary. Let let me tell you, even the GOAT struggled to be himself when Novak Djokovic rose through the tennis ranks.

  2. Arkasia is the weakness of the will, which is the habit of taking action you don’t want to take. Is the impostor syndrome that creeps in when you can’t seem to make a decision.

  3. Google Ads enters its flop era; Perplexity adds Ads to its product

  4. And that’s one reason we like to believe in genius. It gives us an excuse for being lazy. - What you’ll wish you’d know

Hacks of the week

I truly believe you can gaslight yourself to success.

  1. How to automate your job hunting process using ChatGPT

  2. Let me tell you something, when I was in undergrad, Git was the ultimate nightmare, but this is how you “Git Out of Trouble!👿 

  3. How to stand out as a Junior Developer

Cheers to you hacking your week!

Denisse

Reply

or to participate.