题目描述

题目链接：746.使用最小花费爬楼梯

根据示例来看，题目所说的楼梯顶部是数组的下一个位置。

算法原理

解法一

1.状态表示

经验+题目要求，解法一中我们要用到的经验是以…为结尾。
dp[i]表示以i台阶为结尾，也就是到达i台阶所需要的最小花费。

2.状态转移方程

用之前或之后的状态表示当前状态dp[i]的值，根据最近的一步，来划分问题。

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

3.初始化

保证填表的时候不越界

vector<int> dp(n + 1);//需要返回dp[n]所以需要多开一个空间
dp[0] = 0,dp[1] = 0;
//题目要求我们从0台阶或者1台阶开始
//所以到达0台阶和1台阶不需要花费

4.填表顺序

根据状态转移⽅程可得，遍历的顺序是从左往右。

5.返回值

根据状态表⽰以及题⽬要求，需要返回 dp[n] 位置的值。

解法二

1.状态表示

经验+题目要求，解法二中我们要用到的经验是以…开始。
dp[i]表示从i台阶开始，到达楼梯顶部所需要的花费最少是多少。

2.状态转移方程

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

3.初始化

vector<int> dp(n);//和原始数组一样大小即可
dp[n - 1] = cost[n - 1],dp[n - 2] = cost[n - 2];
//前者到达楼梯顶部只需一步，后者需要两步，所以最小花费对应cost数组即可

4.填表顺序

根据状态转移⽅程可得，遍历的顺序是从右往左。

5.返回值

根据状态表⽰以及题⽬要求，需要返回 min(dp[0],dp[1]) 位置的值。

代码实现

解法一：C++

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {//1.创建dp表int n = cost.size();vector<int> dp(n + 1);//2.初始化dp[0] = dp[1] = 0;//3.填表for(int i = 2;i <= n;++i){dp[i] = min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);}//4.返回值return dp[n];}
};

解法一：Java

class Solution {public int minCostClimbingStairs(int[] cost) {// 1. 创建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int n = cost.length;int[] dp = new int[n + 1];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];}
}

解法二：C++

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {//1.创建dp表int n = cost.size();vector<int> dp(n);//2.初始化dp[n - 1] = cost[n - 1],dp[n - 2] = cost[n - 2];//3.填表for(int i = n - 3;i >= 0;--i){dp[i] = min(dp[i + 1] + cost[i],dp[i + 2] + cost[i]);}//4.返回值return min(dp[0],dp[1]);}
};

解法二：Java

class Solution {public int minCostClimbingStairs(int[] cost) {// 1. 创建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int n = cost.length;int[] dp = new int[n];dp[n - 1] = cost[n - 1];dp[n - 2] = cost[n - 2];for (int i = n - 3; i >= 0; i--)dp[i] = Math.min(dp[i + 1], dp[i + 2]) + cost[i];return Math.min(dp[0], dp[1]);}
}