剑指 Offer 10- I. 斐波那契数列
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 ：
输入：n = 2
输出：1
提示：
0 <= n <= 100
思路：
根据递推关系式F(n) = F(n-1) + F(n-2)，很自然会想到递归的方法，其中的终止条件为 n==0，n==1的时候。但是在此采用递归的方法，由于内含大量的重复计算，所以会出现超时的现象。
于是改用动态规划的方法，转移方程仍为F(n) = F(n-1) + F(n-2)，根据题目的特点，每一次迭代的时候，又两个值可以保存下来，留作下一个迭代使用，避免了大量的重复计算。
方法一：递归（超出时间限制，无法通过）
class Solution {
public:
int fib(int n) {
// 以0，1为终止条件
if(n == 0) return 0;
else if(n == 1) return 1;
return (fib(n-1) + fib(n-2)) % 1000000007;
}
};
- 时间复杂度：O(n²)
- 空间复杂度：O(n)
方法二：动态规划
class Solution {
public:
int fib(int n) {
const int mod = 1000000007;
// 用 first 和 last 变量分别保存每一次状态转移时的前一个值 与 后一个值
int first = 0;
int last = 1;
int index = 1;
int sum;
// 特殊情况
if(n == 0) return first;
else if(n == 1) return last;
//循环查找
while(index != n) {
sum = (first + last) % mod;
first = last;
last = sum;
index++;
}
return sum;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)
方法三：矩阵快速幂
官方题解
- 时间复杂度：O(log n)。
- 空间复杂度：O(1)。
剑指 Offer 10- II. 青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 2：
输入：n = 7
输出：21
提示：
0 <= n <= 100
思路：
将青蛙跳台阶问题进行抽象化，令跳 n 阶台阶为 f(n) ，那么就有 f(n) = f(n-1) + f(n-2)
方法一：递归（超出时间限制）
class Solution {
public:
int numWays(int n) {
// 终止条件
if(n == 0 || n == 1) return 1;
if(n == 2) return 2;
// 返回
else return ( numWays(n-1) + numWays(n-2) ) % 1000000007;
}
};
方法二：动态规划
class Solution {
public:
int numWays(int n) {
const int mod = 1000000007;
// 存储变量
int first = 1; // 当 n==0 的时候，f(n)==1
int last = 1; // 当 n==1 的时候，f(n)==1
int index = 1; // index 指向 n=1 （第一次转移方程中的last）
// 特殊情况
if(n == 0) return first;
else if(n == 1) return last;
// 相当于先计算 f(2)
int sum = (first + last) % mod;
while(index != n) {
sum = (first + last) % mod;
first = last;
last = sum;
index++; // 这行代码放在 while 中首行或尾行都可，不会影响结果
}
return sum;
}
};
//附：如果想让 index 指向 n=2，则需要将 while 中的条件更改为 index!=n+1 才可以
- 时间复杂度：O(n)
- 空间复杂度：O(1)
剑指 Offer 63. 股票的最大利润
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
限制：
0 <= 数组长度 <= 10^5
方法：动态规划
在遍历数组的同时，每次都记录下当前最小的价格 minPrice，并计算在该 minPrice 的基础下能获得的利润 profit ,利用得到的利润更新当前的最大利润 maxProfit
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minPrice = INT_MAX;
int profit = 0;
int maxProfit = 0;
for(int i = 0; i < prices.size(); i++) {
if(prices[i] < minPrice) minPrice = prices[i];
profit = prices[i] - minPrice;
if(profit > maxProfit) maxProfit = profit;
}
return maxProfit;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)
Krahets关于斐波那契的解法总结
公式：f(n+1) = f(n) + f(n-1)
总结：
- 递归法：
- 原理：将 f(n+1) 的问题拆分成 f(n) 和 f(n-1) 这两个子问题，进行递归计算，以 f(0) 和 f(1) 作为终止条件
- 缺点：大量的重复计算
- 记忆递归
- 原理：新建一个长度为n的数组，用于存储数字值，避免了重复计算
- 缺点：需要额外的空间
- 动态规划：
- 原理：转移方程
f(n+1) = f(n) + f(n-1)