题目链接

二维斐波那契数列

题目描述

定义一个二维数列 a(i,j) 如下：

  • a(i,j) = 1, 如果 i=1 或 j=1
  • a(i,j) = a(i-1, j) + a(i, j-1), 如果 i > 1 且 j > 1

给定正整数 n 和 m，求 a(n,m) 的值。由于结果可能很大，请对 1,000,000,007 取模。

（注：原题的递推式较为复杂，但可以化简为此处等价的描述。）

解题思路

本题本质上是一个二维的动态规划问题。a(i,j) 的值依赖于它上方 a(i-1,j) 和左方 a(i,j-1) 的值。我们可以将这个数列想象成一个 n x m 的网格。

动态规划（DP）解法： 这个递推关系是动态规划中的一个经典模型，常用于解决"网格路径计数"问题（即从网格左上角到右下角有多少条只向下或向右走的路径）。

  1. DP 状态定义: 我们创建一个二维数组（DP表），dp[i][j] 用来存储 a(i,j) 的值。

  2. DP 初始化（边界条件）: 根据题目定义，当 i=1 或 j=1 时，a(i,j) = 1。这对应于我们网格的第一行和第一列。所以，我们需要将 dp 表的第一行和第一列全部初始化为 1。

  3. DP 递推公式: 对于 i > 1 且 j > 1 的任意位置 (i,j)，其值由上方和左方的值相加得到。递推公式即： dp[i][j] = dp[i-1][j] + dp[i][j-1]

  4. 处理取模: 题目要求结果对 1,000,000,007 取模。由于中间计算结果可能会非常大，甚至超过64位整数的范围，我们必须在每一步加法计算后都进行取模操作。这基于模运算的性质：(A + B) % M = ((A % M) + (B % M)) % M。所以，递推公式应写为： dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007

算法步骤:

  1. 定义模数 MOD = 1000000007。
  2. 读取 n 和 m。
  3. 创建一个 (n+1) x (m+1) 的二维数组 dp。
  4. 使用两层嵌套循环，i 从 1 到 n，j 从 1 到 m。
  5. 在循环内部：
    • 如果 i == 1 或 j == 1，则 dp[i][j] = 1。
    • 否则，dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD。
  6. 循环结束后，dp[n][m] 就是最终答案。

代码

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    const int MOD = 1000000007;
    
    // 创建 (n+1) x (m+1) 的 DP 表
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (i == 1 || j == 1) {
                // 边界条件：第一行或第一列的值为1
                dp[i][j] = 1;
            } else {
                // 递推公式，每次相加后都取模
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
            }
        }
    }
    
    cout << dp[n][m] << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        final int MOD = 1_000_000_007;
        
        // 创建 DP 表
        long[][] dp = new long[n + 1][m + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (i == 1 || j == 1) {
                    // 边界条件
                    dp[i][j] = 1;
                } else {
                    // 递推公式，注意取模
                    dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
                }
            }
        }
        
        System.out.println(dp[n][m]);
    }
}

n, m = map(int, input().split())

MOD = 1_000_000_007

# 创建 (n+1) x (m+1) 的 DP 表，并用 0 初始化
# 注意 Python 中列表索引从0开始，所以大小要额外注意
dp = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, m + 1):
        if i == 1 or j == 1:
            dp[i][j] = 1
        else:
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD

print(dp[n][m])

算法及复杂度

  • 算法：二维动态规划。
  • 时间复杂度：。我们需要填充一个 n x m 大小的表格，每个格子的计算是常数时间。
  • 空间复杂度：。我们使用了一个 n x m 大小的二维数组来存储DP状态。