You are not logged in. Please login at www.codechef.com to post your questions!

×

DP grid problems

Hey there,

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

Thanks!

asked 23 Oct '15, 17:49

sandy999's gravatar image

2★sandy999
39111538
accept rate: 10%


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.

link

answered 23 Oct '15, 18:35

dragonemperor's gravatar image

3★dragonemperor
89321134
accept rate: 10%

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

(23 Oct '15, 18:42) sandy9992★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,085
×2

question asked: 23 Oct '15, 17:49

question was seen: 2,928 times

last updated: 23 Oct '15, 19:05