2 条题解

  • 10
    @ 2023-8-6 23:40:33

    据题目描述,可以使用动态规划的方法来计算从A到B的最短路径数量。

    创建一个二维数组f,大小为(n+1)×(m+1),其中f[i][j]表示从左上角A到位置(i,j)的最短路径数量。

    初始化数组f,将f[1][1]设为1,表示从A到A的最短路径数量为1。

    然后,从位置(2,1)开始进行状态转移。对于每个位置(i,j),通过以下状态转移方程计算最短路径数量:

    • 当i>1且j=1时,f[i][1] = 1;表示从A到第一列其他行的位置的最短路径数量都为1。
    • 当i=1且j>1时,f[1][j] = 1;表示从A到第一行其他列的位置的最短路径数量都为1。
    • 当i>1且j>1时,f[i][j] = f[i-1][j] + f[i][j-1];表示从A到位置(i,j)的最短路径数量等于从A到位置(i-1,j)和从A到位置(i,j-1)的最短路径数量之和。

    最后,得到f[n][m]的值即为从A到B的最短路径数量。

    以下是相应的代码实现:

    #include<bits/stdc++.h>
    using namespace std;
    
    const int MOD = 100007;
    
    int main() {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> f(n + 1, vector<int>(m + 1, 0)); // 初始化f数组,所有元素都设为0
        
        f[1][1] = 1; // 初始化,从A到A的最短路径数量为1
        
        for (int i = 2; i <= n; i++) {
            f[i][1] = 1; // 从A到第一列其他行的位置的最短路径数量都为1
        }
        
        for (int j = 2; j <= m; j++) {
            f[1][j] = 1; // 从A到第一行其他列的位置的最短路径数量都为1
        }
        
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= m; j++) {
                f[i][j] = (f[i-1][j] + f[i][j-1]) % MOD; // 状态转移方程
            }
        }
        
        cout << f[n][m] << endl;
    }
    
    • 6
      @ 2023-7-27 15:41:03
      思路

      创建二维数组 ff,与原始网格的大小相同,f[i][j]f[i][j] 表示从左上角出发到 (i,j)(i,j) 位置的最少路径数量。显然,f[1][1]=1;f[1][1] = 1;。对于 ff中的其余元素,通过以下状态转移方程计算元素值。

      \\(1)当 i>1i>1j=1j=1 时,f[i][1]=1;f[i][1] = 1;

      \\(2)当 i=1i=1j>1j>1 时,f[1][j]=1;f[1][j] = 1;

      \\(3)当 i>1i>1j>1j>1 时,f[i][j]=(f[i1][j]+f[i][j1])f[i][j] = (f[i - 1][j]+f[i][j - 1])%mod;

      最后得到 f[n][m]f[n][m] 的值即为最少路径数量。

      代码
      
      #include<iostream>
      using namespace std;
      int f[105][105];
      int n, m;
      const int mod=100007;
      int main()
      {
          cin >> n >> m;
          for (int i = 1; i <= n; i++)
          {
              f[i][1] = 1;
          }
          for (int j = 1; j <= m; j++)
          {
              f[1][j] = 1;
          }
          for (int i = 2; i <= n; i++)
          {
              for (int j = 2; j <= m; j++)
              {
                  f[i][j] = (f[i - 1][j]+f[i][j - 1])%mod;
              }
          }
          cout << f[n][m];
      

      }

      • 1

      信息

      ID
      352
      时间
      1000ms
      内存
      256MiB
      难度
      1
      标签
      (无)
      递交数
      458
      已通过
      300
      上传者