Dynamic planning - Taking stair climbing with minimum cost as an example

Dynamic programming - Take stair climbing with minimum cost as an example

The title describes each subscript of the array as a ladder , The first i A ladder corresponds to a non negative amount of physical expenditure cost[i]（ Subscript from 0 Start ）.
Every time you climb a ladder, you have to spend the corresponding stamina value , Once you've paid for your strength , You can choose to climb up one ladder or two .
Please find out the lowest cost to reach the top of the floor . At the beginning , You can choose from the subscript to 0 or 1 As the initial step .

determine dp Array and subscript meaning

Observe cost Array understanding question stem ,cost[i] yes Climb up The first i The number of physical strength to spend , Every time I climb i, Must be from i-1, perhaps i-2 Climb up , newly build dp Array

int[] dp = new int[cost.length+1];

Determine the recurrence formula

Observation found that , Give Way dp[i] Corresponding climb cost[i-1] Physical strength expended

dp[i]=Math.min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]);

dp Array initialization

Every dp[i] By the previous dp[i-1] and dp[i-2] By comparison

dp[0]=0;
dp[1]=0;

Determine the traversal order

From the subscript 2 Start , Traverse in turn

Complete code

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