网站建设销售业绩任务,网站开发资格证书,长沙优化公司,中学网站建设方案计划509 斐波那契数#xff08;easy#xff09;
斐波那契数 #xff08;通常用 F(n) 表示#xff09;形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始#xff0c;后面的每一项数字都是前面两项数字的和。也就是#xff1a;
F(0) 0#xff0c;F(1) 1 F(n) F(n - 1)… 509 斐波那契数easy
斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是
F(0) 0F(1) 1 F(n) F(n - 1) F(n - 2)其中 n 1 给定 n 请计算 F(n) 。
思路动态规划
代码实现1
class Solution {
public:int fib(int N) {if (N 1) return N;vectorint dp(N 1);dp[0] 0;dp[1] 1;for (int i 2; i N; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[N];}
};时间复杂度O(n)空间复杂度O(n)
代码实现2
class Solution {
public:int fib(int N) {if (N 1) return N;int dp[2];dp[0] 0;dp[1] 1;for (int i 2; i N; i) {int sum dp[0] dp[1];dp[0] dp[1];dp[1] sum;}return dp[1];}时间复杂度O(n)空间复杂度O(1)
详细解析 思路视频 代码实现文章 70 爬楼梯easy
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
思路动态规划法
代码实现1
// 版本一
class Solution {
public:int climbStairs(int n) {if (n 1) return n; // 因为下面直接对dp[2]操作了防止空指针vectorint dp(n 1);dp[1] 1;dp[2] 2;for (int i 3; i n; i) { // 注意i是从3开始的dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
};时间复杂度O(n)空间复杂度O(n)
代码实现2
// 版本二
class Solution {
public:int climbStairs(int n) {if (n 1) return n;int dp[3];dp[1] 1;dp[2] 2;for (int i 3; i n; i) {int sum dp[1] dp[2];dp[1] dp[2];dp[2] sum;}return dp[2];}
};时间复杂度O(n)空间复杂度O(1)
详细解析 思路视频 代码实现文章 746 使用最小花费爬楼梯easy
给你一个整数数组 cost 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
思路动态规划
代码实现1
class Solution {
public:int minCostClimbingStairs(vectorint cost) {vectorint 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)
代码实现2
// 版本二
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int dp0 0;int dp1 0;for (int i 2; i cost.size(); i) {int dpi min(dp1 cost[i - 1], dp0 cost[i - 2]);dp0 dp1; // 记录一下前两位dp1 dpi;}return dp1;}
};时间复杂度O(n)空间复杂度O(1)
详细解析 思路视频 代码实现文章
