LeetCode uses the minimum cost to climb the stairs----dp problem

Title: Give you an integer array cost, where cost[i] is the cost to climb up the first step of the stairs.Once you pay this fee, you can choose to climb one or two steps up.
You can choose to start the stairs from the steps with index 0 or 1.Please calculate and return the minimum cost to reach the top of the stairs.

Example:

This question is similar to the frog climbing the stairs, you can refer to the common thinking steps of the dp problem

Three steps for a dynamic programming problem:

First step: Define the meaning of the array elements

Second step: Find relationships between array elements

Step 3: Find the initial value

A general idea written in a drawing, with examples

dp[i] represents the minimum cost to reach i
cost[i] represents the cost to climb the i-th stair

i-1 stairs, cost[i-1] to reach subscript i

When 2

Example: when i is equal to 2, to
There are two ways to reach 2
Subscript O goes two steps or subscript 1 goes one step
dpli] means the minimum cost for you to go to the 0th or 1st order, because these twoThe step is the initial step and can be selected, so dp[1/0] is O, only need to consider cost[0] and cost[1] who is bigger. Both cost[0] and cost[1] can reach the second by paying the costThe number written on the step is the set cost, then it is the minimum of 0+2 and O+1 to know dp2=1
Similarly, when i=3, you can go through the first step to 2 or the second step to 1That is, 0+1 and 1+3 take the minimum value to know that dp3 = 1
until it reaches the top, that is, the end of the dp array, and returns to the end of dp.

The code is as follows:

class Solution {public int minCostClimbingStairs(int[] cost) {int n = cost.length;int[] dp = new int[n + 1];dp[0] = dp[1] = 0;for (int i = 2; i <= n; i++) {dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);} }return dp[n];} }}

This question can also be found through analysis that each element is only related to the previous element and the previous element, and you can think about whether it conforms to the scrolling array.

class Solution {public:int minCostClimbingStairs(vector& cost) {int n = cost.size();int prev = 0, curr = 0;//initializationfor (int i = 2; i <= n; i++) {int next = min(curr + cost[i - 1], prev + cost[i - 2]);prev = curr; // scrollcurr = next; // scroll}return curr;}};