Part of course:

Dynamic Programming

- Intuition (and a story)
- Tiling problem
- Other notes

NaN.

Dynamic Programming[ Edit ]

Dynamic programming is a fancy name for *storing intermediate results and re-using the stored result instead of re-computing them each time. *

A story will help. Suppose, one beautiful morning I come to you with a complicated puzzle and challenge you to solve it. You work really hard the entire day and tell me the solution that evening. The next day, I come to you and I ask you the **exact same puzzle**. But since the puzzle was so involved you have forgotten most of the calculations you did, you work them out again and tell me the solution. The third day, I come to you and I ask you the **same exact puzzle again**. This time you're really annoyed, and you decide to not throw away all your calculations and keep them handy so that if I bother you again, you can just show me your solution. The fourth day when I come back to you, and you go *Ha! There's your solution. And I didn't have to think even for a second. *And from that day after, I was never able to trouble you with the puzzle.

What you did is called Dynamic Programming. You said **if I'm going to have to do the same exact calculations 50 times, I might just as well store them somewhere**.

__This tutorial__ describes the above motivation for dynamic programming with examples to a couple of classic problems.

This tutorial covers a couple of __classic tiling problems in dynamic programming__. Once you read the tutorial, I'd like to draw your attention to one point of particular significance. When the solutions begins with

Let T(n) denote the number of ways of tiling an n×2 grid.

it is skipping a lot of steps about the logical reasoning required to ascertain that *n states defined as above will allow us to solve the problem correctly and efficiently*. For example, the second example can't be solved efficiently with just n states, it needs 3n states. The first solution should actually begin with,

In any tiling of the n×2 grid, the bottom left square will either be covered with a vertical tile, or a horizontal tile. If it is covered with a vertical tile, then what remains is a (n-1)×2 grid. If it is covered with a horizontal tile, the only way to cover the top left square is to use another horizontal tile, leaving us with a (n-2)×2 grid. Since the bottom left square can only be tiled in these two distinct ways, the number of ways to tile a n×2 grid is the sum of the number of ways to tile a (n-1)×2 grid and the number of ways to tile a (n-2)×2 grid. Hence, we can define state T(n) = number of ways of tiling an n×2 grid = T(n-1) + T(n-2).

A similar set of reasoning is required to arrive at why we need the 3n states for the second example.

I highly recommend the specific tutorials I've provided links to above. I've gone through about a dozen videos and tutorials online, and 90% of them are terrible at getting the point across.

If you know of tutorials that are simpler but not dumbed down, post it to this discussion. For **trivia** about why Dynamic Programming is named so, a **video** and other information, check out the posts in this discussion.

Read more…(570 words)

Mark as completed

Part of lists:

Previous

[INOI1501] Special Sums (INOI 2015: India)

Next

[ZCO14002] SUPW (ZCO 2014: India)

About the contributor:

Keshav DhandhaniaFormer TopCoder India rank #1, IOI medalist

100%

Loading…

Have a question? Ask here…

Post

Part of course:

Dynamic Programming

- Intuition (and a story)
- Tiling problem
- Other notes

Contributor

Keshav DhandhaniaFormer TopCoder India rank #1, IOI medalist

100%

Ready to join our community?

Sign up below to automatically get notified of new courses, get **reminders** to finish ones you subscribe to, and **bookmark** lessons to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.

Popular Courses

New Courses

Get in touch

Copyright 2016-18, Compose Labs Inc. All rights reserved.