网站插件代码下载,商丘关键词优化推广,高平网站优化公司,123网址大全文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时空频度】九【代码实现】十【提交结果】 一【题目类别】
数组
二【题目难度】
简单
三【题目编号】
746.使用最小花费爬楼梯
四【题目描述】
给你一… 文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时空频度】九【代码实现】十【提交结果】 一【题目类别】
数组
二【题目难度】
简单
三【题目编号】
746.使用最小花费爬楼梯
四【题目描述】
给你一个整数数组 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
七【解题思路】
该题为标准的动态规划题目对于第i个位置cost[i]为第i个位置向上爬的花费dp[i]为到达第i个位置所需要的最小的花费所以可以得到动态转移方程 dp[i] min(cost[i - 1] dp[i - 1], cost[i - 2] dp[i - 2]) 最后返回结果即可具体细节可以参考下面的代码
八【时空频度】
时间复杂度 O ( n ) O(n) O(n) n n n为传入的数组的长度空间复杂度 O ( n ) O(n) O(n) n n n为传入的数组的长度
九【代码实现】
Java语言版
class Solution {public int minCostClimbingStairs(int[] cost) {int n cost.length;// 动态规划数组int[] dp new int[n 1];dp[0] 0;dp[1] 0;// 计算爬楼梯的最小花费到达第 i 层的最小花费由前一层或前两层的最小花费加上当前层的花费决定for (int i 2; i (n 1); i) {dp[i] Math.min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);}// 返回结果return dp[n];}
}Python语言版
class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:n len(cost)# 动态规划数组dp [0] * (n 1)# 计算爬楼梯的最小花费到达第 i 层的最小花费由前一层或前两层的最小花费加上当前层的花费决定for i in range(2, (n 1)):dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2])# 返回结果return dp[n]C语言版
int minCostClimbingStairs(int* cost, int costSize)
{// 动态规划数组int* dp (int *)calloc((costSize 1), sizeof(int));// 计算爬楼梯的最小花费到达第 i 层的最小花费由前一层或前两层的最小花费加上当前层的花费决定for (int i 2; i costSize; i){dp[i] fmin(cost[i - 1] dp[i - 1], cost[i - 2] dp[i - 2]);}int res dp[costSize];free(dp);// 返回结果return res;
}十【提交结果】 Java语言版 Python语言版 C语言版
