509.斐波那契数列
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
题目链接
个人题解
class Solution {
public:int fib(int n) {if(n==0) return 0;if(n==1) return 1;int l=0;int ll=1;for(int i=2;i<=n;i++){int tmp=ll;ll=ll+l;l=tmp;}return ll;}
};
复杂度分析
- 时间复杂度：n
- 空间复杂度：1
解题思路
只求f[n],用两个数记录一下前两个值循环＋就好
70.爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
题目链接
个人题解
class Solution {
public:int climbStairs(int n) { vector<int> v(n,0);v[0]=1;if(n<=1)return v[n-1];v[1]=2;for(int i=2;i<n;i++){v[i]=v[i-1]+v[i-2];}return v[n-1];}
};
复杂度分析
- 时间复杂度：n
- 空间复杂度：n
解题思路
dp入门题，到每一个台阶的方法数等于到上一个台阶的方法数和上上一个台阶的方法数+1
746.使用最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
题目链接
个人题解
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size(),0);dp[0]=cost[0];if(cost.size()<=1) return dp[0];dp[1]=cost[1];for(int i=2;i<cost.size();i++){dp[i]=min(dp[i-1],dp[i-2])+cost[i];}return min(dp[dp.size()-1],dp[dp.size()-2]);}
};
复杂度分析
- 时间复杂度：n
- 空间复杂度：n
解题思路
爬楼梯进阶，dp数组记录的是从这个台阶出发需要的最小消耗，到达该台阶的方法是前两个台阶走2步，或者前一个台阶走一步，需要最小消费那么取min即可，最后加上本步的花费即可。注意要爬到楼顶需要把最后一步的花费加上，而由于可以走一步或两步，返回的应该是这两个的最小值（dp后面再＋一个算出来也一样）
今日总结
dp入门，一维还是比较好想的，dp难点在于想清楚dp记录什么，以及产生式如何产生，一维的dp产生式不会太复杂，但纬度一增加，dp数组要存什么都是个问题，最近学校在讲二维dp，是一听一个不懂啊。