这里主要是记录一个事情:
动态规划题目当中 同一个题目的dp定义可以多种多样
我们定义dp有的时候可以定义为完成第i步的消费, 有的时候可以定义为第i步前的消费总和然后加上cost[i]就是第i步的局部最优
//我一开始想的是这个, 完成第i步的结果这里需要注意dp[1]
class Solution {
public:
int minCostClimbingStairs(const vector<int>& cost) {
int size= cost.size();
vector<int> dp(size);
dp[0]=cost[0];
dp[1]=cost[1];//不能是min(dp_0,dp_1) 如果如此, 就意味着到达dp_1的方式有: 1. 迈两步直接到达, 2.经过两次一小步到达,且未支付第二步的cost
//因此如果要把dp定义为完成第i步, 我们就必须从台阶0,跨一大步 支付一次, 完成第i步
for(int i =2;i<size;i++)
dp[i]=min(dp[i-1],dp[i-2])+cost[i];
return min(dp[size-1],dp[size-2]);//需要选出台阶顶部前一和前二哪个小, 然后不支付任何代价到达顶部, 因为台阶顶部没有cost, 而我们本步骤的已经支付完全, 不再需要再支付, 因为dp的定义就是完成支付后的结果, 也就是意味着我们虽然位于dp_i但是已经支付完全了cost_i
}
};
下面的是官方解法, 也就是dp定义为第i步之前的消耗, 我们跨上去还需要加一个cost_i
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n + 1);//此时需要大一点, 因为我们需要台阶顶的数据, 台阶顶的数据等于i+1步骤之前的最值结果, 台阶顶的数据才是支付完成前面的cost的数据, 因为dp[i]不是完成支付第i步的数据, 还需要到dp[i+1]才是完成第i步的数据
dp[0] = dp[1] = 0;
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];
}
};
作者：力扣官方题解
链接：https://leetcode.cn/problems/min-cost-climbing-stairs/solutions/528955/shi-yong-zui-xiao-hua-fei-pa-lou-ti-by-l-ncf8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。