查找使用wordpress的网站,网站建设 丽水,wordpress自定义按钮,阿里云上如何用iis做网站目录 方法一#xff1a;动态规划
复杂度分析 方法一#xff1a;动态规划
假设数组 cost 的长度为 n#xff0c;则 n 个阶梯分别对应下标 0 到 n−1#xff0c;楼层顶部对应下标 n#xff0c;问题等价于计算达到下标 n 的最小花费。可以通过动态规划求解。
创建长度为 n…目录 方法一动态规划
复杂度分析 方法一动态规划
假设数组 cost 的长度为 n则 n 个阶梯分别对应下标 0 到 n−1楼层顶部对应下标 n问题等价于计算达到下标 n 的最小花费。可以通过动态规划求解。
创建长度为 n1 的数组 dp其中 dp[i] 表示达到下标 i 的最小花费。
由于可以选择下标 0 或 1 作为初始阶梯因此有 dp[0] dp[1] 0.
当 2 ≤ i ≤ 时可以从下标 i−1i-1i−1 使用 cost[i−1] 的花费达到下标 iii或者从下标 i−2i-2i−2 使用 cost[i−2] 的花费达到下标 i。为了使总花费最小dp[i] 应取上述两项的最小值因此状态转移方程如下 dp[i]min(dp[i−1]cost[i−1],dp[i−2]cost[i−2]) 依次计算 dp 中的每一项的值最终得到的 dp[n] 即为达到楼层顶部的最小花费。
C:
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int n cost.size();vectorint dp(n 1);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];}
};
python:
class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:n len(cost)dp [0] * (n 1)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]上述代码的时间复杂度和空间复杂度都是 O(n)。注意到当 i≥2 时dp[i] 只和 dp[i−1] 与 dp[i−2] 有关因此可以使用滚动数组的思想将空间复杂度优化到 O(1)。
C:
class Solution {public int minCostClimbingStairs(int[] cost) {int n cost.length;int prev 0, curr 0;for (int i 2; i n; i) {int next Math.min(curr cost[i - 1], prev cost[i - 2]);prev curr;curr next;}return curr;}
}
python:
class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:n len(cost)prev curr 0for i in range(2, n 1):nxt min(curr cost[i - 1], prev cost[i - 2])prev, curr curr, nxtreturn curr 复杂度分析
时间复杂度O(n)其中 n 是数组 costt 的长度。需要依次计算每个 dp 值每个值的计算需要常数时间因此总时间复杂度是 O(n)。
空间复杂度O(1)。使用滚动数组的思想只需要使用有限的额外空间
相关文章：
