如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY 4.0 （除特别声明或转载文章外）
一 斐波那契数列如此简单
先来看一道 AcWing 上的简单题：
717. 简单斐波那契
以下数列0 1 1 2 3 5 8 13 21 …被称为斐波纳契数列。
这个数列从第3项开始，每一项都等于前两项之和。
输入一个整数N，请你输出这个序列的前N项。
输入格式
一个整数N。
输出格式
在一行中输出斐波那契数列的前N项，数字之间用空格隔开。
数据范围
0<N<46
输入样例：
5
输出样例：
0 1 1 2 3
#include<cstdio>
#include<iostream>
using namespace std;
int main(void)
{
int a = 0, b = 1, n;
scanf("%d", &n);
while(n--)
{
printf("%d ", a);
a += b;
swap(a, b);
}
return 0;
}
这道题对标 LeetCode 上的另一道简单题
这道题中加上了取模运算
剑指 Offer 10- I. 斐波那契数列
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：1
示例 2：
输入：n = 5
输出：5
提示：
0 <= n <= 100
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#define MOD (int)(1e9 + 7)
class Solution {
public:
int fib(int n)
{
int a = 0, b = 1;
while(n-- > 0)
{
a += b;
a %= MOD;
swap(a, b);
}
return a;
}
};
我们也可以用递归来写：
#define MOD (int)(1e9 + 7)
class Solution {
public:
int fib(int n)
{
return f(n);
}
private:
int f(int n)
{
if(n == 0) return 0;
if(n == 1 || n == 2) return 1;
return (f(n - 1) + f(n - 2)) % MOD ;
}
};
但是注意到这道题给的 n 会比较大，所以程序会运行超时。我们可以通过动态规划来合理的剪枝，具体参考下文
二 斐波那契问题还能这样求？
一样很简单吧？我们先来看看 LeetCode 评论区中有那些人才有其他的做法：
面向测试编程
int f[]={0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,134903163,836311896,971215059,807526948,778742000,586268941,365010934,951279875,316290802,267570670,583861472,851432142,435293607,286725742,722019349,8745084,730764433,739509517,470273943,209783453,680057396,889840849,569898238,459739080,29637311,489376391,519013702,8390086,527403788,535793874,63197655,598991529,662189184,261180706,923369890,184550589,107920472,292471061,400391533,692862594,93254120,786116714,879370834,665487541,544858368,210345902,755204270,965550172,720754435,686304600,407059028,93363621,500422649,593786270,94208912,687995182};
int fib(int n){
return f[n];
}
动态规划
上面我们直接递归会运行超时，现在我们合理剪枝
#define MOD (int)(1e9 + 7)
int arr[150];
class Solution {
public:
int fib(int n)
{
arr[1] = 1;
return f(n);
}
private:
int f(int n)
{
if(n == 0 || arr[n]) return arr[n];
arr[n] = (f(n - 1) + f(n - 2)) % MOD ;
return arr[n];
}
};
神奇的 & 运算
#define MOD (int)(1e9 + 7)
class Solution
{
public:
int fib(int n)
{
int arr[2] = {0, 1};
for(int i = 2; i <= n; ++i)
{
arr[i & 1] = (arr[0] + arr[1]) % MOD;
}
return arr[n & 1];
}
};
矩阵快速幂
const int MOD = 1000000007;
const int N = 50;
struct mat
{
int m[N][N];
mat()
{
memset(m, 0, sizeof(m));
}
// 单位矩阵
void setUnitMat()
{
for (int i = 0; i < N; ++i)
m[i][i] = 1;
}
};
class Solution {
public:
int fib(int n)
{
if (n <= 1)
return n;
mat q;
q.m[0][0] = q.m[0][1] = q.m[1][0] = 1;
q.m[1][1] = 0;
mat ans = fastPow(q, n - 1);
return ans.m[0][0];
}
private:
const int n = 2;
mat&& fastPow(mat q, int n)
{
// ans 初始为单位矩阵
mat ans;
ans.setUnitMat();
while (n > 0)
{
if (n & 1)
ans = matrixMul(q, ans);
q = matrixMul(q, q);
n >>= 1;
}
return std::move(ans);
}
mat&& matrixMul(mat& q, mat& M)
{
mat ans;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
for (int k = 0; k < n; ++k)
{
ans.m[i][j] += (q.m[i][k] * M.m[k][j]) % MOD;
}
}
}
return std::move(ans);
}
};
205. 斐波那契
输入样例：
0
9
999999999
1000000000
-1
::heavy_check_mark: 自己的编译器上可以运行，放上去段错误了
去掉右值引用即可通过
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<iostream>
using namespace std;
#define MOD (int)10000
#define N 2
struct mat
{
int a[N][N];
mat()
{
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
a[i][j] = 0;
}
}
}
void setUnitMat()
{
for (int i = 0; i < N; ++i)
a[i][i] = 1;
}
};
mat&& matMul(mat& a, mat& b)
{
mat res;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
for (int k = 0; k < N; ++k)
{
res.a[i][j] += (a.a[i][k] * b.a[k][j]) % MOD;
res.a[i][j] % MOD;
}
}
}
return std::move(res);
}
mat&& fastPow(mat q, int n)
{
mat u;
u.setUnitMat();
while (n > 0)
{
if (n & 1) u = matMul(u, q);
q = matMul(q, q);
n >>= 1;
}
return std::move(u);
}
int main(void)
{
int n;
mat q;
q.a[0][0] = q.a[0][1] = q.a[1][0] = 1;
q.a[1][1] = 0;
scanf("%d", &n);
while (n != -1)
{
if (n <= 1)
{
printf("%d\n", n);
scanf("%d", &n);
continue;
}
mat res = fastPow(q, n - 1);
printf("%d\n", res.a[0][0] % MOD);
scanf("%d", &n);
}
return 0;
}
AC 代码
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<iostream>
using namespace std;
#define MOD (int)10000
#define N 2
struct mat
{
int a[N][N];
mat()
{
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
a[i][j] = 0;
}
}
}
void setUnitMat()
{
for (int i = 0; i < N; ++i)
a[i][i] = 1;
}
};
mat matMul(mat& a, mat& b)
{
mat res;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
for (int k = 0; k < N; ++k)
{
res.a[i][j] += (a.a[i][k] * b.a[k][j]) % MOD;
res.a[i][j] % MOD;
}
}
}
return res;
}
mat fastPow(mat q, int n)
{
mat u;
u.setUnitMat();
while (n > 0)
{
if (n & 1) u = matMul(u, q);
q = matMul(q, q);
n >>= 1;
}
return u;
}
int main(void)
{
int n;
mat q;
q.a[0][0] = q.a[0][1] = q.a[1][0] = 1;
q.a[1][1] = 0;
scanf("%d", &n);
while (n != -1)
{
if (n <= 1)
{
printf("%d\n", n);
scanf("%d", &n);
continue;
}
mat res = fastPow(q, n - 1);
printf("%d\n", res.a[0][0] % MOD);
scanf("%d", &n);
}
return 0;
}
斐波那契额数列的大数运算
观察到 f[100] 为 687995182 当 n 很大时会超过整形的范围
#include<cstdio>
#include<cstring>
int prev[100], cur[100], tmp[100];
int prevPos = 0, curPos = 0;
void print()
{
// 数字在数组中存放时低位在前，需要倒序输出
for(int i = prevPos; i >= 0; --i)
printf("%d", prev[i]);
printf(" ");
}
void add()
{
memcpy(tmp, cur, sizeof(cur));
// 更新 prevPos
// 更新原因：prev 中大于 prevPos 的元素肯定是 0 ，但是 cur 中的元素可能会进位
prevPos = curPos;
for(int i = 0; i <= prevPos; ++i)
{
cur[i] += prev[i];
// 进位的前提是在 i + 1 在 prevPos 范围内
if(cur[i] > 9 && i + 1 <= prevPos)
{
cur[i] -= 10;
++cur[i + 1];
}
}
// 如果最高位大于 9，需要增加向后增加高位，此时需要更新 curPos
if(cur[prevPos] > 9)
{
cur[prevPos] -= 10;
// 增加最大位
++curPos;
++cur[curPos];
}
memcpy(prev, tmp, sizeof(cur));
}
int main(void)
{
cur[0] = 1;
int n;
scanf("%d", &n);
while(n--)
{
print();
add();
}
return 0;
}
三 走向离谱
873. 最长的斐波那契子序列的长度
如果序列 X_1, X_2, …, X_n 满足下列条件，就说它是 斐波那契式 的：
n >= 3 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2} 给定一个严格递增的正整数数组形成序列，找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。
（回想一下，子序列是从原序列 A 中派生出来的，它从 A 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）
示例 1：
输入: [1,2,3,4,5,6,7,8]
输出: 5
解释:
最长的斐波那契式子序列为：[1,2,3,5,8] 。
示例 2：
输入: [1,3,7,11,12,14,18]
输出: 3
解释:
最长的斐波那契式子序列有：
[1,11,12]，[3,11,14] 以及 [7,11,18] 。
提示：
3 <= A.length <= 1000
1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
（对于以 Java，C，C++，以及 C# 的提交，时间限制被减少了 50%）
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/length-of-longest-fibonacci-subsequence 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
暴力
使用 set
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr)
{
int N = arr.size();
set<int> S;
for(auto& i : arr)
S.insert(i);
int ans = 0;
for(int i = 0; i < N - 1; ++i)
{
for(int j = i + 1; j < N; ++j)
{
int f1 = arr[i], f2 = arr[j];
int cnt = 2;
// 继续向后寻找斐波那契数
while(S.find(f1 + f2) != S.end())
{
++cnt;
f1 = f1 + f2;
swap(f1, f2);
}
ans = max(ans, cnt);
}
}
// 斐波那契数列最少为 3 个
return ans >= 3 ? ans : 0;
}
};
时间复杂度：O(n^2logn)(while循环的复杂度是 logn)
空间复杂度：O(n)
动态规划
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr)
{
int N = arr.size();
unordered_map<int, int> idx;
// 建立元素与下标对应关系
for(int i = 0; i < N; ++i)
idx[arr[i]] = i;
unordered_map<int, int> longest;
int ans = 0;
for(int i = 0; i < N - 1; ++i)
{
for(int j = i + 1; j < N; ++j)
{
// arr[k] + arr[i] == arr[j]
if(arr[j] - arr[i] < arr[i] && idx.count(arr[j] - arr[i]))
{
// k 应该从 idx 中寻找得到下标
int k = idx[arr[j] - arr[i]];
longest[i * N + j] = longest[k * N + i] + 1;
ans = max(ans, longest[i * N + j] + 2);
}
}
}
return ans;
}
};
1414. 和为 K 的最少斐波那契数字数目
给你数字 k ，请你返回和为 k 的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。
斐波那契数字定义为：
F1 = 1 F2 = 1 Fn = Fn-1 + Fn-2 ， 其中 n > 2 。 数据保证对于给定的 k ，一定能找到可行解。
示例 1：
输入：k = 7
输出：2
解释：斐波那契数字为：1，1，2，3，5，8，13，……
对于 k = 7 ，我们可以得到 2 + 5 = 7 。
示例 2：
输入：k = 10
输出：2
解释：对于 k = 10 ，我们可以得到 2 + 8 = 10 。
示例 3：
输入：k = 19
输出：3
解释：对于 k = 19 ，我们可以得到 1 + 5 + 13 = 19 。
提示：
1 <= k <= 10^9
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
三个证明至关重要：
解 不可能 含有两个连续的斐波那契数
解 可以不 使用重复的斐波那契数
对于目标数 k，设 k = 2Fx 2Fx = Fx + Fx = F(x - 2) + F(x - 1) + F(x) = F(x - 2) + F(x + 1) 2Fx > F(x - 1) + F(x) 所以 F(x + 1) 必在小于 k 的斐波那契数中，所以可以用 F(x + 1) 与 F(x - 2) 的组合替换 2F(x)解一定包含小于等于 k 的最大斐波那契数
k 中要包含小于等于 k 的最大斐波那契数(
F(max))。如果这一点我们可以接受的话，那么如果k - F(max) > 0，此时的问题相当于之前的子问题。子问题中 k 为k - F(max)继续寻找下一个F(max)即可
class Solution {
public:
int findMinFibonacciNumbers(int k)
{
vector<int> fib(2, 1);
// top 记录 fib 最高一位的下标
int top = 1;
while(fib[top] <= k)
{
fib.push_back(fib[top - 1] + fib[top]);
++top;
}
int ans = 0;
// 从后向前遍历，如果 k >= fib[i] 则减去，ans 增加 1
for(int i = top; i >= 0; --i)
{
if(k >= fib[i])
{
++ans;
k -= fib[i];
}
if(!k) break;
}
return ans;
}
};
842. 将数组拆分成斐波那契序列
给定一个数字字符串 S，比如 S = “123456579”，我们可以将它分成斐波那契式的序列 [123, 456, 579]。
形式上，斐波那契式序列是一个非负整数列表 F，且满足：
0 <= F[i] <= 2^31 - 1，（也就是说，每个整数都符合 32 位有符号整数类型）； F.length >= 3； 对于所有的0 <= i < F.length - 2，都有 F[i] + F[i+1] = F[i+2] 成立。 另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。
返回从 S 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。
示例 1：
输入："123456579"
输出：[123,456,579]
示例 2：
输入: "11235813"
输出: [1,1,2,3,5,8,13]
示例 3：
输入: "112358130"
输出: []
解释: 这项任务无法完成。
示例 4：
输入："0123"
输出：[]
解释：每个块的数字不能以零开头，因此 "01"，"2"，"3" 不是有效答案。
示例 5：
输入: "1101111"
输出: [110, 1, 111]
解释: 输出 [11,0,11,11] 也同样被接受。
提示：
1 <= S.length <= 200 字符串 S 中只含有数字。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
int length;
class Solution {
public:
vector<int> splitIntoFibonacci(string S)
{
vector<int> ans;
length = S.length();
bruteforce(S, ans, 0, 0);
return ans;
}
private:
bool bruteforce(string& S, vector<int>& ans, int size, int idx)
{
// S 遍历完成
if(idx == length)
{
// 如果 ans 元素个数大于 3，返回真
return size >= 3;
}
for(int i = idx; i < length; ++i)
{
// 位数大于 1 的数不能以 0 开头
if(S[idx] == '0' && i > idx)
break;
long long num = stoll(S.substr(idx, i - idx + 1));
// 不能超过 32-bit int 的最大值
if(num > INT_MAX) break;
// 如果 ans 长度大于 2 且 num 大于 ans 前两个元素之和，不用继续向后找
if(size >= 2 && (long long)ans[size - 2] + ans[size - 1] < num)
break;
if(size <= 1 || (long long)ans[size - 2] + ans[size - 1] == num)
{
ans.push_back(num);
// 更新状态
if(bruteforce(S, ans, size + 1, i + 1))
return true;
// 回溯
ans.pop_back();
}
}
return false;
}
};