代码随想录算法训练营Day38|LC509 斐波那契数列LC70 爬楼梯LC746 使用最小花费爬楼梯

一句话总结：难的还在后头呢。

原题链接：509 斐波那契数列

甚至用不上数组，用两个变量滚动交替即可完成。

class Solution {public int fib(int n) {if (n < 2) return n;int pre = 0, cur = 1;int ans = 0;for (int i = 2; i <= n; ++i) {ans = pre + cur;pre = cur;cur = ans;}return ans;}
}

原题链接：70 爬楼梯

经典动态规划，同样利用两个变量即可解决问题。

class Solution {public int climbStairs(int n) {int pre = 1, cur = 1;for (int i = 2; i <= n; ++i) {int sum = pre + cur;pre = cur;cur = sum;}return cur;}
}

 原题链接：746 使用最小花费爬楼梯

两个变量搞定一切。

class Solution {public int minCostClimbingStairs(int[] cost) {int n = cost.length;int pre = 0, cur = 0;for (int i = 2; i <= n; ++i) {int next = Math.min(pre + cost[i -2], cur + cost[i - 1]);pre = cur;cur = next;}return cur;}
}