如何在动态规划中将递归值存储在我的地图中

Question

我正在尝试使用动态编程找到从左上角网格到右下角网格的方法数量，因此我使用 map<pair<int, int>, int> 进行记忆。

当我尝试在地图中插入 k 值时，它并未存储在我的地图中，仅存储了我的 c 和 r 整数。为什么会这样？

#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
#include <stdbool.h>
#include <map>
using namespace std;
int grid(int r , int c , map<pair<int,int> ,int>& m1);
int main()
{
    map<pair<int ,int>,int> m1;
    int k=grid(2,3 ,m1);
    cout<<k<<endl;
    for(auto& it1:m1){
        cout<<it1.first.first<<"\t"<<it1.first.second<<"\t"<<it1.second<<endl;
    }
}

int grid(int r , int c , map<pair<int,int> ,int>& m1)
{
    if(r==0 || c==0) return 0;
    if(r==1 && c==1) return 1;
    if(m1[{r,c}]!=NULL){return m1[{r,c}];}
    int k=grid(r-1,c,m1)+grid(r,c-1,m1);
    m1.insert({{r,c},k});
    cout<<"k:"<<k<<endl;
    return grid(r-1,c,m1)+grid(r,c-1,m1);
}

输出：--------------------------------

k:1
k:1
k:1
k:1
k:1
k:2
k:1
k:1
k:3
k:1
k:1
k:1
k:1
k:1
k:2
k:1
k:1
3
1       2       0
1       3       0
2       1       0
2       2       0
2       3       0

Answer 1

您使用 m1[{r,c}] 在地图中检查值的方式将创建条目（如果条目不存在）。当您稍后尝试使用 m1.insert 添加密钥时，将不会添加该值，因为该密钥已经存在。

您可以将插入内容替换为

m1[{r,c}] = k;

或使用find或lower_bound检查密钥是否存在。这还有一个好处，即不会对同一个键进行多次查找。

auto it = m1.lower_bound({r,c});
if (it != m1.end) return it->second;  // key found, return value
int k = ...;
m1.insert(it, {{r,c}, v});

使用insert的提示版本利用之前不成功的查找来避免遍历地图来定位正确的插入位置。

如何在动态规划中将递归值存储在我的地图中

How to store the recursive value in my map in dynamic programing

c++

dynamic-programming

c++11