算法训练（leetcode）第二十八天 | 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

509. 斐波那契数

leetcode题目地址

递归

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

// c++
class Solution {
public:int fib(int n) {if(n<2) return n;return fib(n-1) + fib(n-2); }
};

循环

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

//c++
class Solution {
public:int fib(int n) {if(n<2) return n;int a=0, b=1;for(int i=2; i<=n; i++){swap(a, b);b += a;}return b;}
};

动态规划

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

// c++
class Solution {
public:int fib(int n) {if(n<2) return n;vector<int> dp(n+1, 0);dp[1]=1;for(int i=2; i<=n; i++){dp[i] = dp[i-1] + dp[i-2]; }return dp[n];}
};

70. 爬楼梯

leetcode题目地址

本质上还是斐波那契数列。用递归会在45处时间超限。

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

// c++
class Solution {
public:int climbStairs(int n) {if(n<=2) return n;int a=1, b=2;for(int i=3; i<=n; i++){swap(a,b);b+=a;}return b;}
};

746. 使用最小花费爬楼梯

leetcode题目地址

动态规划。使用dp记录到达第i个楼梯所需要花费的费用。起始位置不需要支付费用，而起始位置可以是0和1，因此0、1位置的dp值为0.从2开始计算当前位置所需的最小花费。到达第i层的费用等于到达前一步的最小花费+前一步的花费。具体来说，若前一步是爬1个台阶到达第i层，则第i层的花费为cost[i-1]+dp[i-1]；若前一步是爬2个台阶到达第i层，则第i层的花费为cost[i-2]+dp[i-2]。

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

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

优化空间：上面的代码中起始每次都是只操作前面两个空间，因此只使用两个变量来计算既可。

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

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