题目描述
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。 - 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。
示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1] 输出：6 解释：你将从下标为 0 的台阶开始。 - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。 - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。 - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。 - 支付 1 ，向上爬一个台阶，到达楼梯顶部。 总花费为 6 。
提示：
2 <= cost.length <= 10000 <= cost[i] <= 999
思路
动态规划 递推公式
首先，到达第n阶台阶有两种方式
- 1.由n-1阶台阶，前进一步到达 - 花费为前面花费总和加上第n-1阶的花费: sum(n-1)+cur(n-1)
- 2.由n-2阶台阶，前进两步到达 - 花费为前面花费总和加上第n-2阶的花费: sum(n-2)+cur(n-2)
所以，第n阶最小花费应取二者较小值
sum(n) = min(sum(n-1)+cur(n-1), sum(n-2)+cur(n-2))
C语言版
int minCostClimbingStairs(int* cost, int costSize) { int i = 0; int num1 = 0; int num2 = 0; int num3 = 0; if (costSize < 2) { return fmin(cost[0], cost[1]); } for (i = 2; i <= costSize; i++) { num3 = fmin(num1 + cost[i - 2], num2 + cost[i - 1]); num1 = num2; num2 = num3; } return num3; }
C++版
//746_使用最小花费爬楼梯 /* 动态规划 递推公式 首先，到达第n阶台阶有两种方式 - 1.由n-1阶台阶，前进一步到达 - 花费为前面花费总和加上第n-1阶的花费: sum(n-1)+cur(n-1) - 2.由n-2阶台阶，前进两步到达 - 花费为前面花费总和加上第n-2阶的花费: sum(n-2)+cur(n-2) 所以，第n阶最小花费应取二者较小值 sum(n) = min(sum(n-1)+cur(n-1), sum(n-2)+cur(n-2)) */ class Solution { public: int minCostClimbingStairs(vector<int>& cost) { if (cost.size() < 2) { return min(cost[0], cost[1]); } vector<int> ret; ret.push_back(0); ret.push_back(0); for (int i = 2; i <= cost.size(); i++) { ret.push_back(min(ret[i - 1] + cost[i - 1], ret[i - 2] + cost[i - 2])); } return ret[cost.size()]; } }; //优化空间复杂度 class Solution { public: int minCostClimbingStairs(vector<int>& cost) { if (cost.size() < 2) { return min(cost[0], cost[1]); } int num1 = 0, num2 = 0, num3 = 0; for (int i = 2; i <= cost.size(); i++) { num3 = min(num1 + cost[i - 2], num2 + cost[i - 1]); num1 = num2; num2 = num3; } return num2; } };
Python版
#746_使用最小花费爬楼梯 ''' 动态规划 递推公式 首先，到达第n阶台阶有两种方式 - 1.由n-1阶台阶，前进一步到达 - 花费为前面花费总和加上第n-1阶的花费: sum(n-1)+cur(n-1) - 2.由n-2阶台阶，前进两步到达 - 花费为前面花费总和加上第n-2阶的花费: sum(n-2)+cur(n-2) 所以，第n阶最小花费应取二者较小值 sum(n) = min(sum(n-1)+cur(n-1), sum(n-2)+cur(n-2)) ''' class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: if len(cost) < 2: return min(cost) dp = list() dp.append(0) dp.append(0) for i in range(2, len(cost) + 1): dp.append(min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])) return dp[len(cost)] #优化空间复杂度 class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: if len(cost) < 2: return min(cost) num1 = 0 num2 = 0 for i in range(2, len(cost) + 1): num3 = min(num2 + cost[i - 1], num1 + cost[i - 2]) num1 = num2 num2 = num3 return num2
