C++动态规划求解网格路径代码map无法插入值问题求助

• 核心问题是all_path函数的table参数采用了值传递，每次函数调用都会生成独立的map副本，递归过程中对table的插入操作只会作用于当前副本，不会同步到其他调用的map实例，因此缓存永远无法命中，统计变量c的数值始终为0。
• 当前代码能输出正确的路径总数，是因为退化成了无缓存的暴力递归，所有子问题均重复计算，仅未触发缓存命中逻辑。

将all_path的table参数修改为引用传递，所有递归调用共享同一个map实例即可，修改后完整可运行代码如下：

#include<bits/stdc++.h>
using namespace std;
static int c=0;

// table参数加&改为引用传递
int all_path(int i, int j, int m, int n, map<pair<int,int>, int>& table )
{   
    if(table.find(make_pair(i,j))!=table.end())
    {
        c++;
        return table[make_pair(i,j)];
    }
    if(i==m-1 && j==n-1)
        return 1;
    if(i>=m || j>=n)
        return 0;
    return table[make_pair(i,j)] = all_path(i+1, j, m, n, table) + all_path(i, j+1, m, n, table);
}

int main()
{
    int m, n;
    map<pair<int,int>, int> table;
    cin>>m>>n;
    int temp = all_path(0, 0, m, n, table);
    cout<<temp<<endl;
    cout<<"saved calls: "<<c<<endl;
    return 0;
}

• map的查找插入开销较高，可替换为二维数组做缓存，运行效率更高。
• 该问题也可以用组合数学直接计算：路径总数等于$C_{m+n-2}^{m-1}$，即从总共m+n-2步中选m-1步向下（剩余为向右）的组合数，时间复杂度为O(min(m,n))。

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