计算 mXn 矩阵从左上角到右下角的所有可能路径

Question

我应该 return 在 n*m 矩阵中从左上角到右下角的可能路径数。这是我的代码。

class Solution {
 public:
 map<pair<int,int>,long long int>mp;
   long long int numberOfPaths(int m, int n){
       if(n==1 || m==1)
       {
           return 1;
       }
       if(mp[make_pair(n,m)]!=0)
       return mp[make_pair(n,m)];
       mp[make_pair(n,m)]=numberOfPaths(n-1,m)+numberOfPaths(n,m-1);
       return mp[make_pair(n,m)];
   }
};

我有很多解决这个问题的方法，但我有兴趣找出我的代码中的错误。我得到了输入 19 和 71 的错误答案。

Answer 1

我认为您在这里遗漏了 Mod 10^9 + 7 问题，请仔细阅读问题，它必须在那里以避免溢出，您必须回答 mod 10^9 +7

Answer 2

简答：您预期的答案是错误的。输入 19 和 71 的正确答案确实是 2418561960739869780.

长答案：

首先，始终保持代码格式 - 它可以帮助您自己和 reader 此类问题收集一些阅读问题的动力。这是格式稍微好一点的版本：

class Solution {
public:
    map<pair<int, int>, long long int> mp;
    long long int numberOfPaths(int m, int n) {
        if(n == 1 || m == 1) {
            return 1;
        }
        if(mp[make_pair(n, m)] != 0) return mp[make_pair(n, m)];
        mp[make_pair(n, m)] = numberOfPaths(n-1, m) + numberOfPaths(n, m-1);
        return mp[make_pair(n, m)];
    }
};

其次，始终尝试包含可重现的代码。当您只共享一个 class 定义时，reader 很难理解您是如何使用它的。

第三，我知道你这样做是作为动态规划的一部分。但是这种方法是蛮力的（正如之前的评论中所指出的那样）。对此的数学解决方案是 (m-1) + (n-1) C (m-1)，因为您有尽可能多的组合。由于优化了乘法而不是重复加法，因此计算速度也更快。

88 C 18确实是2418561960739869780.

计算 mXn 矩阵从左上角到右下角的所有可能路径

Count all possible paths from top left to bottom right of a mXn matrix

c++

algorithm

dynamic-programming