[动态规划] (三)LeetCode 746. 使用最小花费爬楼梯(两种解法)
文章目录
- [动态规划] (三)LeetCode 746. 使用最小花费爬楼梯(两种解法)
- 题目解析
- 解题思路
- 状态表示
- 状态转移方程
- 初始化和填表顺序
- 返回值
- 状态表示
- 状态转移方程
- 初始化和填表顺序
- 返回值
- 代码实现
- 总结
746. 使用最小花费爬楼梯
题目解析
(1) cost[i]数组是从i位置向上爬的费用
(2) 支付一次费用有两种选择:爬一次或者爬两次
(3) 可以从第0或1台阶开始爬
(4) 爬到顶楼需要的话费,从示例1可以看出,顶楼指的是cost.size。
解题思路
解法一:
状态表示
题目:最小花费
猜测:以i位置为结尾(大胆猜测,推导不出状态转移方程再重新猜)
dp[i]:题目+猜测= 到达i
位置时的最小花费
状态转移方程
用i
之前或者i
之后的状态,推出dp[i]
到达i
有两种可能:i
-1爬一步,i
-2爬两步
那dp[i]就是,到达i
-1位置前的花费+当前位置的花费(i-1
)或者是到达i
-2位置前的话费+当前位置的花费(i-2
)。
对它们两个取最小值即可。
dp[i] = min(cost[i-1]+dp[i-1], cost[i-2]+dp[i-2])
初始化和填表顺序
初始化:题目告诉我们,可以从0或者1位置开始,即dp[0] = dp[1] = 0。
填表顺序:避免越界,从左向右填
返回值
返回n位置即可,dp[n]
解法二:
状态表示
题目:最小花费
猜测:从i位置为起点
dp[i]:题目+猜测= 从i为起点到顶楼的最小花费
状态转移方程
以i为起点,有两种选择:到达i+1,再到顶楼或者到达i+2,再到顶楼
正好,我们的dp[i]是从i到顶楼的花费,所以
dp[i] = min(cost[i]+dp[i+1], cost[i]+dp[i+2])
初始化和填表顺序
初始化:我们要用的是i+1
和i+2
位置的值,最后是从n-1或者n-2到顶楼
dp[n-1] = cost[n-1], dp[n-2] = cost[n-2]
填表顺序:我们这里是反着推导的,所以是从右往左填表的。
返回值
dp[i]表示的是从i
位置开始到楼顶的最小花费,所以最后是返回dp[0]和dp[1]中小的那个即可。
代码实现
法一
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n+1);
for(int i = 2; i <= n; i++)
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
return dp[n];
}
};
法二
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n+1);
for(int i = 2; i <= n; i++)
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
return dp[n];
}
};
总结
细节:得出状态表示后,尝试推导状态转移方程。