題目鏈接：746.使用最小花費爬樓梯

方法:動態規劃

假設數組cost的長度為n,則n個階梯分別對應下標0到n- 1,樓層頂部對應下標n,問題等價于計算達到下標n的最小花費。可以通過動態規劃求解。

創建長度為n + 1的數組dp,中dp[i] 表示達到下標i的最小花費。

于可以選擇下標0或1作為初始階梯，因此有dp[0] = dp[1]= 0。

當2≤i≤n時，可以從下標i-1使用cost[i- 1]的花費達到下標i,或者從下標i-2使用costli - 2]的花費達到下標i。為了使總花費最小，dp[i] 應取上述兩項的最小值，因此狀態轉移方程如嚇:

dp[i]= min(dp[i - 1] + costi- 1],dp[i- 2] + cost[i - 2])

依次計算dp中的每-項的值， 最終得到的dp[n]即為達到樓層頂部的最小花費。

#include<iostream> #include<algorithm> 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的算法题目——使用最小花费爬楼梯(动态规划)的全部內容，希望文章能夠幫你解決所遇到的問題。

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