“This is the 39th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

I. Problem description

Each subscript of the array is a ladder, and the ith ladder corresponds to a non-negative cost cost[I] (the subscript starts at 0).

Every time you climb a ladder, you have to spend your stamina. Once you’ve paid your stamina, you can choose to climb one ladder or two.

Please find the lowest cost to reach the top of the floor. To start, you can choose to start with an element with subscript 0 or 1.

The least cost of climbing stairs

Two, the title requirements

Sample 1:

Input: cost = [10, 15, 20] Output: 15 Explanation: The lowest cost is to start at cost[1] and then walk two steps to the top of the ladder, which costs 15 in total.Copy the code

Example 2:

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] Output: 6 Explanation: The lowest cost is to start at cost[0], pass through the ones one by one, skip cost[3], and cost 6 altogether.Copy the code

inspection

2. The recommended time is 15 to 30 minutesCopy the code

Third, problem analysis

This is also a typical dynamic programming problem, dynamic programming has not done can see this entry problem solution:

Day 34: Frog jumps step

Here’s our three-step routine:

Step 1: Understand what it means

They want to find the minimum cost to get to the top of the floor, so our dynamically programmed array dp[I] represents the minimum cost to get from subscript 0 to subscript I.

Pay attention to

This one wants to get to the top of the building, so even though we index the array to n minus 1, we want to get to n.

Step 2 Variable initialization:

Only two variables need to be initialized:

dp[0]=0;
dp[1]=0;
Copy the code

The third step:

Assuming I is 2, how does dp[2] take advantage of the first two DP relationships?

0->2 requires two hops, costing DP [0]+cost[0] 1->2 requires one hop, costing DP [1]+cost[1]Copy the code

Dp [2] can only be obtained from the above two expressions, so we can choose a small one. The same applies to dp[3] and DP [4].

So dp [I] = min (dp [I – 1) + cost] [I – 1, dp [I – 2) + cost [I – 2));

Three steps, call it a day!

Four, coding implementation

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
    int i,n=cost.size(a);/ / initialization
    int dp[n+2];
    dp[0] = dp[1] =0;// The variable is initialized
    for (i=2; i<=n; i++) { dp[i] =min(dp[i- 1]+cost[i- 1],dp[i2 -]+cost[i2 -]);// Rule induction
    }
    return dp[n];// Output the result}};Copy the code

V. Test results