DP grid problems

Hey there,

Suggestions for some good DP problems involving grids to try out for starters?

Thanks!

Can you please define beginner? I mean do you have any experience with dynamic programming?

If no, the simplest grid problem is finding number of ways to reach a cell from origin with given constraints. For example, suppose you start from cell 0,0 and on each move you can go to one cell right or one cell top/down(depending on which cell is considered 0,0). Find number of ways to reach cell m,n.

This is in my view the simplest one.

Then try variations on it. Like each cell has some number, find a path in which sum of these numbers is minimum/maximum.

Other variation would be finding shortest path between two grids with movement constraints etc.

This link is for beginners might help :Dynamic Programming - Problems involving Grids | HackerEarth

Also you can try

P.s. some of them might not be dp, may be flood fill etc. But all are grid based

3 Likes

Ok, not exactly beginner. I do have some experience with DP,and have tried a few grid problems before, just would like to practise some more

Thanks a lot!