C++ code to find all possible path in a grid, from (0, 0) to (m, n), can move only right or down - Dynamic programming approach

Question

I have written the code but the values not getting inserted into the map. otherwise, it is giving correct output(no. of paths).

#include<bits/stdc++.h>
using namespace std;
static int c=0;
map<pair<int,int>, int> 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;
    else
     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 i=0, j=0, n, temp,m; 
    cin>>m>>n;
    temp=all_path(i,j,m,n,table);
    cout<<temp<<endl;  cout<<"saved calls: "<<c;
    return 0;
}

You're passing the table by value. Read about reference parameters in your favourite C++ book. (And avoid global variables.) — molbdnilo, Sep 03 '21 at 09:07
Does this answer your question? [What's the difference between passing by reference vs. passing by value?](https://stackoverflow.com/questions/373419/whats-the-difference-between-passing-by-reference-vs-passing-by-value) — Korosia, Sep 03 '21 at 09:09
What you're trying to do is memoization, but not dynamic programming. Dynamic programming is an *optimization* method, and counting all possible paths in a grid has nothing to do with optimization. — Evg, Sep 03 '21 at 09:27
btw, there are still some use cases for `make_pair`, but this isnt one. `table[make_pair(i,j)]` -> `table[{i,j}]` — 463035818_is_not_an_ai, Sep 03 '21 at 09:42
thanks for your responses. I got the error. I have to pass the table by reference. — Kunwar Prashant, Sep 03 '21 at 10:21

score 2 · Answer 1 · edited Sep 03 '21 at 14:57

2

I don't think you need dynamic programing for this as you can get the correct value. by the formula enter image description here

that is because from m+n steps that are needed in order to get to (m,n) you would need to move right n times and all the other times you would go down.

read more on choose here : https://en.wikipedia.org/wiki/Combination

edited Sep 03 '21 at 14:57

Evg

25,259
5
41
83

answered Sep 03 '21 at 09:28

rooren

84
4

Computing binomial coefficients from factorials is inefficient and prone to arithmetic overflows. It is much easier to calculate them as elements of the Pascal triangle, which is (unsurprisingly) exactly what the original program is trying to do. – n. m. could be an AI Sep 03 '21 at 15:30

C++ code to find all possible path in a grid, from (0, 0) to (m, n), can move only right or down - Dynamic programming approach

1 Answers1