746. 使用最小花費爬樓梯 - 力扣（LeetCode）

1、狀態表示：

題目意思即：cost[i]代表從第i層向上爬1階或者2階，需要花費多少力氣。如cost[0]，代表從第0階爬到第1階或者第2階需要cost[0]的力氣。

一共有cost.size()階臺階，爬到第cost.size()階臺階最少需要花費多少力氣。

即dp[i]代表，爬到第i階最少需要花費多少力氣。

2、狀態轉移方程：

首先：一次可以爬1階或者2階，并且花費的力氣都是一樣的。

那么dp[2]，可以0-》2，從0爬到2花費的力氣即為cost[0]；也可以1-》2，從1爬到2花費的力氣即為cost[1]，但是前提是要爬到第1階，而爬到第1階所花費的力氣為dp[1]，則1-》2花費的力氣為do[1] + cost[1]。所以dp[2] = min{cost[0],dp[1] + cost[1]}。

那么對于dp[i]：可以i-2-》i，從i-2爬到i花費的力氣為cost[i-2]，而爬到第i-2階所花費力氣為dp[i-2],則力氣為dp[i-2] + cost[i-2]；可以i-1-》i，從i-1爬到i花費的力氣為cost[i-1]，而爬到第i-1階所花費力氣為dp[i-1],則力氣為dp[i-1] + cost[i-1]。

所以dp[i] = min{dp[i-2] + cost[i-2],dp[i-1] + cost[i- 1]}。

3、初始化：

題目所說，可以從第0層開始爬，也可以從第1層開始爬。所以初始化dp[0] = dp[1] = 0。

4、遍歷順序：

肯定是最高臺階由小變大遍歷，即i從小到大遍歷。

5、返回值：

返回dp[cost.size()]，即n階臺階。

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();//一共n階臺階//越界檢查if(n == 0 || n == 1) return 0;vector<int> dp(n+1);//dp表，大小為n+1dp[0] = 0,dp[1] = 0;//初始化dp[0] = dp[1] = 0for(int i= 2;i<=cost.size();i++)//遍歷順序{dp[i] = std::min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]);//狀態轉移方程}return dp[cost.size()];//返回值}
};