回忆的网格旅行解决方案作为常规递归解决方案运行

Question

问题陈述：

您在N Grid的M的左上角。如果您只能向下或右移动，您可以到达右下方的几种方法？

观察：

• 找到了一个类似的问题（ 2D网格旅行（动态编程） - 递归解决方案工作但没有记忆），但我认为它在调试时无法解决我的问题
• ，我发现内存映射访问或 v 不使用
• 该代码作为对Gridtraversal问题的简单递归解决方案，即记忆的部分根本不运行。

代码：

#include <iostream>
#include <cstring>
#include <map>
using namespace std;

string find_target(string target, map<string, unsigned>& v) {
    if (v.find(target) != v.end()) {
        cout << v[target] <<endl;
        return target;
    }
    return "0";
}

int gridTraveller(unsigned m, unsigned n, map<string, unsigned>& v) {
    
    string a =  m + "," + n;
    a = find_target(a, v);

    // Debugging
    // cout << a << " ";

    if (strcmp(a.c_str(), "0")!=0) return v[a];
    if (m==1 && n==1) return 1;
    else if (m==0 || n==0) return 0;
    
    v[a] = gridTraveller(m-1, n, v) + gridTraveller(m, n-1, v);
    return v[a];
}

int main() {
    cout<<"Enter no of rows: ";
    unsigned row; cin >> row;
    cout<<"Enter no of columns: ";
    unsigned col; cin >> col;
    map <string, unsigned> visited;
    cout << gridTraveller(row, col, visited);
    return 0;
}

常规输出：

Enter no of rows: 3
Enter no of columns: 2
3

调试输出：

Enter no of rows: 3
Enter no of columns: 2
0 0 0 0 0 0 0 0 0 0 0 0 0 3

Answer 1

找到了错误！事实证明，我对地图键有问题 - 在串联之前，我必须将 int 转换为 String 。还找到了一种更好的方法来检查键是否已经存在于地图中

string int_to_str(int x) {
   stringstream s;
   s << x;
   return s.str();
}

unsigned gridTraveller(unsigned m, unsigned n, map<string, unsigned>& v) {
    string a = int_to_str(m) + "," + int_to_str(n);
    if (v.count(a)) return v[a];
    ...
}