Help me to so this problem
Dynamic Programming problem
please refer to this article for theory and code
No man, help me to solve this question asked in one of my interview questions
Test Case:
1 2
0 1
ans: 3
please tell me the approach you initially used to solve this question
Point to consider:
- question asking count number of ways from (1,1) to (m,n) then it s dp problem quite easy to understand.
2.now we have only 3 moves to travel move1: move diagonally any number time
move2: move right any numbe of time without crossing the grid boundary.
move 3: move down any number of times without crossing the grid boundary - Now if that’s only the condition given than I can easily solve using dp.but problem is there is a number of parking lots given at grid[i][j] that represent either we use that parking:
now again another condition implies that we have two conditon:
i. if we use that parking then again we are open to use three of the path dialgonal, down and right.
ii. if we not use that parking then we couldnot stay at that cell and move from that cell as same in direction where we come from previous cell to that cell.
3.Now i use lot trick to solve but only able to solve 2-3 test case out of 10 but that was wrong approach i used before .intially i try to solve by tring on every number of parking given at particular cell by simple loop for grid[i][j] number of time and compute way by moving in 3 of the direction but here i failed because i didn’t tackle the condition in which if i really don’t want to use that parking i simply pass through that cell without stopping there.
here question asked for possible distinct way that’s the dp one m pretty sure help me solve