【算法与数据结构】746、LeetCode使用最小花费爬楼梯

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

二、解法

  思路分析：本题可以从0阶或者1阶台阶开始，每次爬楼梯所需的花费是之前的花费dp[i]+从本层向上爬所需的cost[i]$dp[i]+cost[i]$。可能到达第i阶台阶的情况有两种：从第i-2阶台阶一次性爬两步；从第i-1阶台阶一次性爬一步。因为要找到最小的花费，可以知道动态数组的表达式为：$dp[i]=min(dp[i-2]+cost[i-2]，dp[i-1]+cost[i-1])$。
  程序如下：

class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int> dp(cost.size() + 1);// 楼顶
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i <= cost.size(); i++) {
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
}
return dp[cost.size()];
}
};

复杂度分析：

• 时间复杂度： $O(n)$。
• 空间复杂度：$O(n)$。

三、完整代码

# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;

class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int> dp(cost.size() + 1);// 楼顶
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i <= cost.size(); i++) {
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
}
return dp[cost.size()];
}
};

int main() {
vector<int> cost = { 1, 100, 1, 1, 1, 100, 1, 1, 100, 1 };
Solution s1;
int result = s1.minCostClimbingStairs(cost);
cout << result << endl;
system("pause");
return 0;
}

end

原文地址：https://blog.csdn.net/qq_45765437/article/details/135497539

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！