题解 | 二维斐波那契数列(使用迭代法+记忆化剪枝）

#include <iostream>
using namespace std;
long long memo[1005][1005];
long long fib(int n,int m){
    long long res=0;
    if(n==1||m==1){
        return memo[n][m]=1;
    }
    if(memo[n][m]){return memo[n][m];}
    res=(fib(n-1,m)+fib(n,m-1))%(1000000007);
    memo[n][m]=res;
    return res;
}
int main() {
    int n,m;
    cin>>n>>m;
    cout<<fib(n,m);
    return 0;
}

由题目给的公式可以很容易知道，当n或者m中有一个为1时，f(n,m)=1

核心递推公式：f(n,m) = f(n-1,m) + f(n,m-1)

由此我们就可以很容易写出以下基本迭代写法：

#include <iostream>

using namespace std;

long long fib(int n,int m){

if(n==1||m==1){

return 1;

}

return (fib(n-1,m)+fib(n,m-1))%(1000000007);

}

int main() {

int n,m;

cin>>n>>m;

cout<<fib(n,m);

return 0;

}

但是这样有大量子问题被重复计算了导致计算量爆大，运行超时

于是我们可以引入记忆数组memo来进行剪枝，每次计算都保留到数组里面以便于直接下次调用，省去大量计算：

if(n==1||m==1){

return memo[n][m]=1;

}

if(memo[n][m]){return memo[n][m];}

res=(fib(n-1,m)+fib(n,m-1))%(1000000007);

memo[n][m]=res;