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 :https://www.hackerearth.com/notes/dynamic-programming-problems-involving-grids/

Also you can try

https://www.codechef.com/problems/PUPPYCTPUPPYCT

https://www.codechef.com/problems/GRID

https://www.codechef.com/problems/NITA11

https://www.codechef.com/NOV12/problems/MANYLEFT

https://www.codechef.com/problems/GRID/

https://www.codechef.com/problems/IITK1P09

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

1 Like

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!