數組的每個索引做為一個階梯，第?i個階梯對應著一個非負數的體力花費值?cost[i](索引從0開始)。

每當你爬上一個階梯你都要花費對應的體力花費值，然后你可以選擇繼續爬一個階梯或者爬兩個階梯。

您需要找到達到樓層頂部的最低花費。在開始時，你可以選擇從索引為 0 或 1 的元素作為初始階梯。

示例?1:

輸入: cost = [10, 15, 20]
輸出: 15
解釋: 最低花費是從cost[1]開始，然后走兩步即可到階梯頂，一共花費15。
?示例 2:

輸入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
輸出: 6
解釋: 最低花費方式是從cost[0]開始，逐個經過那些1，跳過cost[3]，一共花費6。

本題一個容易忽略的是如果他離最后一個臺階只有兩步，那么他可以一步跨上去而不計算最后一個臺階的花費

public class Solution746 {
?? ?public static int minCostClimbingStairs(int[] cost) {
? ? ? ? int t = cost.length;
? ? ? ? int i;
? ? ? ? int[] dp = new int[t+1];
? ? ? ? dp[0] = cost[0];
? ? ? ? dp[1] = cost[1];
? ? ? ? for(i=2;i<t;i++)
? ? ? ? {
? ? ? ? ?? ?dp[i]=java.lang.Math.min(dp[i-1], dp[i-2])+cost[i];
? ? ? ? }
? ? ? ? return java.lang.Math.min(dp[t-1],dp[t-2]);
? ? }
?? ?public static void main(String[] args)
?? ?{
?? ??? ?int[] cost = {1,1,0,0};
?? ??? ?System.out.println(minCostClimbingStairs(cost));
?? ?}
}
?

?

總結

以上是生活随笔為你收集整理的动态规划--Leetcode746的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。