二维网格旅行（动态编程） - 递归解决方案有效但不记忆

Question

问题陈述 - 有一个尺寸为 m x n 的二维网格，你在左上角，当你只能向下或向右移动时，找出有多少种方法可以到达右下角。

该代码使用无序映射，其中键是字符串，如 "2,3" 、 "1,2"（树中的节点），它们的值是整数（no.of 达到该值的方法节点）。

以下是为递归函数 gridTraveller(2,3) 提供正确输出的代码；输出为 3。但是，当仅使用记忆函数 gridTravelerMemo(2,3) 编译时，会出现地址边界错误。

#include<bits/stdc++.h>
unsigned gridTraveller(unsigned m, unsigned n);
unsigned gridTravelerMemo(unsigned m, unsigned n);
std::string keyConvertedToString(unsigned m, unsigned n);

int main(int argc, char const *argv[])
{               
    //std::cout<<gridTraveller(2,3);
    std::cout<<gridTravelerMemo(2,3);
    return 0;
}

unsigned gridTraveller(unsigned m, unsigned n)
{
    if (m == 1 && n == 1) return 1;
    if (m == 0 || n == 0) return 0;
    return gridTraveller(m-1, n) + gridTraveller(m, n-1);
}

std::string keyConvertedToString(unsigned m, unsigned n)
{
    return (std::to_string(m) + ',' + std::to_string(n));
}

unsigned gridTravelerMemo(unsigned m, unsigned n)
{   
    std::unordered_map<std::string, int> memo;
    const std::string key = keyConvertedToString(m,n);
    if (memo.count(key) > 0) 
        return memo.at(key);
    memo[key] = gridTravelerMemo(m-1, n) + gridTravelerMemo(m, n-1);
    return memo.at(key);
}

尝试打印密钥并且它有效，所以这行可能有问题：

memo[key] = gridTravelerMemo(m-1, n) + gridTravelerMemo(m, n-1);

但不确定是什么；请问有人吗？

Answer 1

您需要在函数中添加断路器和初始化条件gridTravelerMemo

更新：

另外一个问题是，你每次都在初始化无序映射 gridTravelerMemo 函数，因此您还需要从函数中删除它并将其初始化为全局函数。

代码：

 #include<bits/stdc++.h>
unsigned gridTraveller(unsigned m, unsigned n);
unsigned gridTravelerMemo(unsigned m, unsigned n);
std::string keyConvertedToString(unsigned m, unsigned n);

std::unordered_map<std::string, int> memo;

int main(int argc, char const *argv[])
{
    //std::cout<<gridTraveller(2,3);
    std::cout<<gridTravelerMemo(2,3);
    return 0;
}

unsigned gridTraveller(unsigned m, unsigned n)
{
    if (m == 1 && n == 1) return 1;
    if (m == 0 || n == 0) return 0;
    return gridTraveller(m-1, n) + gridTraveller(m, n-1);
}

std::string keyConvertedToString(unsigned m, unsigned n)
{
    return (std::to_string(m) + ',' + std::to_string(n));
}

unsigned gridTravelerMemo(unsigned m, unsigned n)
{

    const std::string key = keyConvertedToString(m,n);
    if (memo.count(key) > 0)
        return memo.at(key);
    if(m==0 || n==0) return 0;
    if(m==1 && n==1) return 1;
    memo[key] = gridTravelerMemo(m-1, n) + gridTravelerMemo(m, n-1);
    return memo.at(key);
}

二维网格旅行（动态编程） - 递归解决方案有效但不记忆

2D grid travel (Dynamic Programming) - recursive solution working but not memoized one

c++

stl

dynamic-programming

graph-theory

graph-algorithm