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

Question

I m trying to find the number of ways you can get from the top-left grid to the bottom right grid using dynamic programing so I m using map<pair<int, int>, int> for memoization.

When I try to insert the k value in the map it doesn't get stored in my map, only my c and r integers get stored. Why is this happening?

#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);
}

Output:-----------------------------------

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

See [Why should I not #include ?](https://stackoverflow.com/q/31816095/3422102) and [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/q/1452721/364696) — David C. Rankin, Jun 05 '21 at 04:45
Should also change to `if (m1.find({r,c}) != m1.end()) { return m1[{r,c}]; }` to properly test is the key `{r,c}` already exists instead of using `NULL`. — David C. Rankin, Jun 05 '21 at 04:59

score 2 · Accepted Answer · answered Jun 05 '21 at 03:53

The way you check for a value in the map with m1[{r,c}] will create the entry if it does not exist. When you try to add the key later with m1.insert, the value will not be added because the key already exists.

You can either replace the insert with

m1[{r,c}] = k;

or use find or lower_bound to check if the key exists. This also has the advantage of not doing multiple lookups for the same key.

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});

Using the hint version of insert takes advantage of the previous unsuccessful lookup to avoid traversing the map to locate the correct place to insert it.

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

1 Answers1