Intuition (and a story)

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.

Tiling problem

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.

Other notes

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.