算法经典题型23

动态规划法求解斐波那契数列第n项，要求用两种算法思路（一种空间复杂度为O(n)，一种空间复杂度小于O(n)）。

用到的思想—动态规划法
博主用到的环境：Win7, CodeBlocks等。

一、代码

#include <iostream>
using namespace std;

long fabi1(int n,long *s);

int main()
{
	int i;
	long s[1024];
	for(i=0;i<1024;i++)
	{
		s[i]=0;
	}
	for(i=0;i<35;i++)
	{
		cout <<fabi1(i+1,s)<<" ";
	}
	cout <<endl;
	return 0;
}

long fabi1(int n,long *s)
{
	if(n <=1 )
	{
		return n;
	}
	s[n-1]=fabi1(n-1,s);
	return s[n-1]+s[n-2];
}

二、测试

总结

谢谢宝宝们的阅读，有问题的话评论@我，没问题的话点个赞再走哦~

logN求Fibonacci数列第N项

• 斐波那契数列通项公式 $F(i)=F(i-1)+F(i-2)$
• 以下介绍两种复杂度为$O(logN)$的算法
• 两种方法思想类似

1. 动态规划

• 当我们尝试将$F(i-1)$和$F(i-2)$进行继续拆解时（始终保持两项），发现两项的系数始终是斐波那契数列中的某一相邻两项
• 因此，F(i)一定可以可以由4个项组成
  • $F(i)=F(i-a)F(i-x)+F(i-b)F(i-(x-1))$
  • 当$a=0$时则为$F(i)=F(2)F(i-1)+F(1)F(i-2)$
  • 且a，b，x具有一定关系

思路

a，b，x有多种可能
此时需要算4个小项才能合并到1个大项
若这4个项中有相同的项，则可以简化计算
此外，越大的项，计算的复杂度越大，反之越小

因此我们可以想到取 $i/2$ 附近的项

• 通过递推得（也可以用较小的$i$找找规律）
  • 当$i$为奇数时，$F(i)=F^2(i/2+1)+F^2(i/2)$
  • 当$i$为偶数时，$F(i)=F(i/2+1)\ast F(i/2)+F(i/2)\ast F(i/2-1)$

即我们将一个递推项分成2或3项分别计算后再合并

• 可以分析复杂度为$O(logN)$

• 注：在实际程序实现中，不能直接return F(i/2+1)*F(i/2)+F(i/2)*F(i/2-1)，这样会造成计算冗余
• 应该先保存下结果，计算后return

DP代码

int Fibonacci(int x) // logN
{
    if (x == 1 || x == 2) return 1;
    if (x % 2 != 0)
    {
        int F1 = Fibonacci(x / 2 + 1), F2 = Fibonacci(x / 2);
        return F1 * F1 + F2 * F2;
    }
    else
    {
        int F1 = Fibonacci(x / 2 + 1), F2 = Fibonacci(x / 2), F3 = Fibonacci(x / 2 - 1);
        return F1 * F2 + F2 * F3;
    }
}

2. 矩阵分治

• 结合矩阵的知识，我们可以知道斐波那契数列符合
• 
• 于是随着等号右边中的斐波那契项的项数$i$降低，该矩阵就不断左乘

因此可以基于矩阵结合律计算若干项矩阵乘积，再左乘$F(1)andF(2)$

• 设该矩阵为A
• 则$A^n=A^{n/2}\ast A^{n/2}$
• 其中$A^{n/2}$只需计算一项
• 依次类推

这就是快速幂的思想

快速幂讲解

代码

int[2][2] Matrix(int x)
{
    int a[2][2] = { { 1, 1 }, { 0, 1 } };
    if (x == 1) return a;
    int b[2][2] = Matrix(x / 2);
    if (x % 2 == 0) return b * b; // 省略矩阵乘法
    return b * b * a;
}

一、基本概念

动规是非递归的一种代码可以保存下来一些过程的解
1. 把原来的为标题分解成几个相似的子问题
2. 所有的子问题都只需要解决一次
3. 储存子问题的解

动规本质：是对问题状态的定义和状态方程的定义（状态以及状态之间的递归关系）

动态规划问题一般从以下四个角度考虑：
1. 状态定义
2. 状态间的转移方程定义
3. 状态的初始化
4. 返回的结果

状态定义的要求：定义的状态一定要形成递推关系。

一句话概括：三特点四要素本质

适用场景：最大值/最小值。可不可行。是不是，方案个数。

递归的思想还是要从实际问题切入来理解，

二、斐波那契数列

这道题是剑指Offer的一道题，非常经典

描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
$n\le 39n\le 39$

斐波那契数列

2.1 递归解法

首先，递归解法很容易理解，但是递归对n有很大的要求，太大会导致栈帧溢出，究其原因是每次返回的都是两个函数的递归，随着n的增大造成指数级增长。

class Solution {
public:
    int Fibonacci(int n) {
        if(n == 0)
            return 0;
        if(n == 1 || n ==2)
            return 1;
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
};

这道题递归解法空间复杂度是O(2^(n-1))，时间复杂度O(N)，这道题使用动规如何解呢？

2.2 动规解法

我们列出四要素：

问题：
数列第n项的值

状态F(i)：
数列第i项的值

转移方程：
$$F(i)=F(i-1)+F(i-2)$$
初始状态至少有两项：
F(0) = 0
F(1) = 1
返回值
F(n)

我们可以用一个数组把中间某一项的值保存下来，后一项的值就等于前两项值之和

class Solution {
public:
    int Fibonacci(int n) {
        //时间复杂度O（n）空间复杂度O(n)
        vector<int> F(n + 1, 0);    //定义数组保存每一次的状态值
        //初始化：F[0] = 0, F[1] = 1
        F[0] = 0;
        F[1] = 1;
        //状态方程求解F[i] = F[i - 1] + F[i - 2]
        for(int i = 2; i <= n; ++i)
        {
            F[i] = F[i - 1] + F[i - 2];
        }
        return F[n];
};

这道题时间复杂度O（n），空间复杂度O(n)，依然可以继续优化

2.3 迭代解法

class Solution {
public:
    int Fibonacci(int n) {     
        //时间复杂度O(n),空间复杂度是O(1)
        //fn1代表f(n - 1), fn2代表f(n - 2)
        int fn1 = 1;
        int fn2 = 0;
        int fn;
        if(n <= 1)
            return n;
        for(int i = 2; i <=n; ++i)
        {
            fn = fn1 + fn2;
            fn2 = fn1;
            fn1 = fn;
        }
        return fn;
    }
};

通过迭代，这道题时间复杂度O(n),空间复杂度是O(1)