Destination with turns - Dynamic Programming Coding test question

help
,
1

Th following question came in a recent on campus test. My understanding is that it requires a dynamic programming approach. However, since I wasn’t able to solve it, I may very well be wrong is this regard.

Here is the question (in simplied words):

Given a matrix of N rows and M columns, find the number of ways to move from top-left to bottom-right corner. You are only allowed to move in the right direction or in the downward direction. Moreover, you cannot take more than two consecutive steps in a particular direction. Since the answer can be large, output it to mod 10^9 + 7.

The constraints were as follows: 1<=N,M<=1000

I have been trying to devise a strategy to solve this but nothing fruitful has yet been achieved. Any help in this regard will be highly appreciated.

2

Is any test case available? Actually, I am a noob. I found this question interesting and I have coded the solution, I want to check if mine is correct? :grin:

3

For N = 3 and M = 4 the output was 7

4

Let dp[i][j] be the number of paths from top-left to point (i,j).
However, here we also have to consider how we arrived at this point. Suppose we arrived from the top (moved downwards), then we have to go right.
So now there are only 2 possibilities on how we arrived at the point. So we need an extra parameter.Let’s say a boolean variable f.
So dp[i][j][0] is the number of paths if we arrived at (i,j) by moving downwards and dp[i][j][1] is the number of paths if we arrived at (i,j) by moving towards the right.
See if you can find a recursive relationship from this.

5

lol i am getting 9 for N=3,M=4
My code:

#include<bits/stdc++.h>
#define F first;
#define S second;
#define PB push_back;
#define er erase;
//Done by vaibhavgadag
#define MP make_pair;
#define fastio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
const long long MOD = 1e9 + 7;
const long long INF = 1e9 + 7;
typedef long long int ll;
using namespace std;
ll dp[1001][1001],n,m;

ll solve(ll i,ll j)
{
if(i==n-1 and j==m-1)
{
return 1;
}
else if(i>n-1 or j>m-1)
{
return 0;
}
else if(dp[i][j]!=-1)
{
return dp[i][j];
}

else
{
    //twice down then move right
    if(i==(j+2))
    {
        return dp[i][j]=solve(i,j+1)%MOD;
    }
    //twice right then move down
    else if(j==(i+2))
    {
        return dp[i][j]=solve(i+1,j)%MOD;
    }
    else
    {
        return dp[i][j]=(solve(i+1,j)%MOD+solve(i,j+1)%MOD)%MOD;
    }
}

}

int main()
{

fastio;
ll i=0,j=0;
cin>>n>>m;
memset(dp,-1,sizeof(dp));
cout<<solve(i,j)%MOD<<endl;

return 0;

}
Can anyone help me to figure out what’s wrong
Thank you in advance

6

Sir can u check my code once?and help me