题解 | 二维斐波那契数列

#include <iostream>
using namespace std;

int main() {
    int n,m;
    cin>>n>>m;
    int a[1001][1001]={0};
    a[1][1]=1;
    /*(1e9+7) 是一个 double 类型的表达式，不能用于取模运算 %，因为 % 只能用于整数。

    把 1e9 + 7 改为整型常量即可：
    */
    const int MOD = 1e9 + 7;  // 声明常数
    for(int i=1;i<=n;i++){

        for(int j=1;j<=m;j++){
            if((i==1)&&(j==1)) continue;
            
            if (i == 1) {
                a[i][j] = a[i][j - 1]; // 第一行只能从左边来
            } 
            else if (j == 1) {
                a[i][j] = a[i - 1][j]; // 第一列只能从上边来
            }
            
            else {
                a[i][j]=(a[i-1][j]+a[i][j-1])%MOD;
                
            }
        }
    }
    cout << a[n][m] << endl;
    return 0;
}

🧠 一、什么是动态规划（Dynamic Programming, 简称 DP）？

动态规划是一种将大问题拆解为多个子问题，并利用子问题的解来构建大问题解的算法思想。

它的核心思想是：

避免重复计算 —— 通过 保存子问题的答案（通常用数组），以后遇到相同子问题时直接查表，而不是重新计算。

🔁 二、动态规划的三个要素

1. 状态表示（状态定义）：用一个数组 dp[i][j] 或 dp[i] 表示某个子问题的解。
2. 状态转移方程（递推关系）：如何从较小的状态得到当前状态。比如二维斐波那契数列的状态转移：
3. 初始状态（边界）：最基本的情况怎么处理，通常是 dp[0] 或 dp[1] = ...。