题解 | 二维斐波那契数列

#include <stdio.h>
#define mod 1000000007

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    int shuzu[n + 1][m + 1];

    //全部填充零
    for (int i = 0; i < n + 1; i++){
        for (int j = 0; j < m + 1; j++){
            shuzu[i][j] = 0;
        }
    }

    if (n >= 1 && m >= 1){
        shuzu[1][1] = 1;
    }
    if (n >= 2 && m >= 1){
        for (int i = 2; i < n + 1; i++){
            shuzu[i][1] = shuzu[i - 1][1] % mod;
        }
    }
    if (n >= 1 && m >= 2){
        for (int j = 2; j < m + 1; j++){
            shuzu[1][j] = shuzu[1][j - 1] % mod;
        }
    }

    if (n >= 2 && m >= 2){
        for (int i = 2; i < n + 1; i++){
            for (int j = 2; j < m + 1; j++){
                shuzu[i][j] = (shuzu[i - 1][j] + shuzu[i][j - 1]) % mod;
            }
        }
    }

    //填充的时候取模防止溢出
    //最后取模多一层保护，也可以不取模
    int result = shuzu[n][m] % mod;    //取模不是/号记住了
    printf("%d", result);
    return 0;
}



// 错误做法：只在最后取模
// shuzu[i][j] = shuzu[i-1][j] + shuzu[i][j-1];  // 可能这里就溢出了！
// 最后：result = shuzu[n][m] % mod;  // 但此时已经错了

// 正确做法：每一步都取模
// shuzu[i][j] = (shuzu[i-1][j] + shuzu[i][j-1]) % mod;  // 始终保持小数字