统计递归子问题个数

分治策略是算法设计的重要策略之一，该策略的基本思想是把问题进行分解成一些子问题，通过子问题的求解完成对原问题的求解。其关键是分解和合并，好的分解或合并方法才会产生高效的分治算法。

分治策略设计出的算法最常见的就是递归算法。但是如果在分解时，分解出的子问题有很多是重复的，那么这样的分治（递归）算法求解问题的效率就非常低。例如斐波那契数问题，如果采用递归求解，算法效率非常低：O(2^n)。而如果采用递推求解(动态规划自底向上求解)，算法效率非常高：O(n)。

Question

现在请你编写程序，统计计算一个斐波那契数时分解出的各子问题的个数。

斐波那契数的定义如下：

Fib(0)=0
Fib(1)=1
Fib(n)=Fib(n-1)+Fib(n-2)

输入：一个整数n，即计算Fib(n)

输出：n+1行，即各个子问题的值及该子问题的个数。

Example

Input

Output

Fib(0)=0,spn=3
Fib(1)=1,spn=5
Fib(2)=1,spn=3
Fib(3)=2,spn=2
Fib(4)=3,spn=1
Fib(5)=5,spn=1

分析

一大段分治思想的介绍，递归与递推的区别，我以为这题用递归会超时，要用递推求解，于是入坑……

这题要统计子问题个数，递推或者递归加备忘录根本没重复的计算怎么统计……

不死心的我又仔细研究递推子问题个数的规律，发现子问题个数正好是一个反着的斐波那契数列（结尾元素特殊处理），所以可以正向递推求数列，反向递推求子问题个数。

不过特殊情况研究的有点头疼，暂时就不搞了，下面给出的是老老实实递归求解的程序。

Answer

#include <iostream>
#include <cstring>
using namespace std;
int*spn;
int*data;
int fib(int n){
    spn[n]++;
    if(n==0){
        data[0]=0;
        return 0;
    }
    if(n==1){
        data[1]=1;
        return 1;
    }
    int res=fib(n-1)+fib(n-2);
    data[n]=res;
    return res;
}
int main()
{
    int n;
    cin>>n;
    spn=new int[n+1];
    data=new int[n+1];
    memset(spn,0,(n+1)*sizeof(int));
    memset(data,-1,(n+1)*sizeof(int));
    data[0]=0;
    data[1]=1;
    fib(n);
    for(int i=0;i<=n;i++){
        cout<<"Fib("<<i<<")="<<data[i]<<",spn="<<spn[i]<<endl;
    }
    return 0;
}

最后修改于 2019-05-17