m×n矩阵仅向右/向下移动的路径计数问题：递归记忆化解法在19×71测试用例中失效求助

Let's break down exactly why your code fails for this test case and walk through practical fixes. First, a quick reminder: counting paths from the top-left to bottom-right of an m×n matrix (only right/down moves) is a classic combinatorics problem— the number of paths equals the binomial coefficient C((m-1)+(n-1), m-1) (choosing (m-1) downward steps out of (m+n-2) total steps).

The Root Cause of Your Failure #

Your code crashes for m=19, n=71 due to integer overflow:

• For this test case, the total steps are 19+71-2=88. The binomial coefficient C(88,18) is 10400600279520— a number way larger than the maximum value of a 32-bit int (~2.1e9). Storing this value in an int causes overflow, leading to incorrect (often negative or garbage) results.
• Your memory map uses int as the value type, which amplifies this issue.

Minor (But Worth Fixing) Inefficiencies #

1. Slow Key Generation: Using to_string(m)+","+to_string(n) to create map keys adds unnecessary string operation overhead.
2. Redundant Lookup: Checking both (m,n) and (n,m) works, but we can simplify this by leveraging symmetry (paths for m×n are identical to n×m) to cut down on duplicate work.

Fixed Recursive Code with Memoization #

This version fixes the overflow issue and optimizes the memoization logic:

#include <unordered_map>
#include <utility>

// Custom hash function for pair<int, int> (required for unordered_map)
struct PairHash {
    template <class T1, class T2>
    size_t operator () (const std::pair<T1, T2>& p) const {
        auto hash1 = std::hash<T1>{}(p.first);
        auto hash2 = std::hash<T2>{}(p.second);
        // Combine hashes to avoid collisions
        return hash1 ^ (hash2 << 1);
    }
};

std::unordered_map<std::pair<int, int>, long long, PairHash> memo;

long long countPaths(int m, int n) {
    // Base cases
    if (m == 1 && n == 1) return 1;
    if (m == 0 || n == 0) return 0;

    // Leverage symmetry to reduce duplicate calculations
    if (m > n) std::swap(m, n);
    auto key = std::make_pair(m, n);

    // Check memoization cache
    if (memo.find(key) != memo.end()) {
        return memo[key];
    }

    // Use long long to prevent overflow during calculation
    long long result = countPaths(m-1, n) + countPaths(m, n-1);
    memo[key] = result;
    return result;
}

Even Better: Iterative Dynamic Programming (No Recursion Overhead) #

If you want to avoid recursion entirely and boost efficiency, this iterative DP approach uses optimized space and runs faster:

#include <vector>
#include <algorithm>

long long countPaths(int m, int n) {
    // Optimize space by using the smaller dimension for our array
    if (m > n) std::swap(m, n);
    
    // dp[j] = number of paths to reach column j in the current row
    std::vector<long long> dp(m, 1);
    
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < m; ++j) {
            dp[j] += dp[j-1];
        }
    }
    
    return dp[m-1];
}

This version uses O(min(m,n)) space and runs in O(mn) time— no recursion stack, no hash map overhead, and no overflow issues for your test case.

Handling Extremely Large Values #

If you need to compute paths for very large m/n (e.g., m=100, n=100), even long long won't suffice (C(198,99) is ~9e58). In that case, you'll need to implement a big integer class or use a third-party arbitrary-precision arithmetic library.

内容的提问来源于stack exchange，提问作者Tarsh