This post is about how to come up with solutions applying dynamic programming when all I can think about is brutal force.

Let’s start from a simple problem.

## I. Climbing stairs

70. Climbing Stairs: count ways to reach the top of a stair case with n steps, supposing you can take 1 or 2 steps at a time.

Let f(n) be the number of ways to reach the top. If you take 1 step for the last climb, there will be f(n-1) ways; if you take 2 steps for the last climb, there will be f(n-2) ways. So the problem can be broken down sub-problems like this: f(n) = f(n-1) + f(n-2).

This is easy to implemented using recursion.

However, the time complexity of this implementation is O(2^n). It is exponential, and it will cause stack overflow eventually.

If you execute the recursive function on the paper, you will find that there are many redundanct calculation. Take n = 6 for example, we have to calculate f(4) twice and f(3) three times.

We can introduce memorization here to reduce redundancy.

A little improvement, but it still depends on function stack, which might lead to stack overflow.
So we should get rid of recursion, but how?
As shown in the diagram above, the function is executed from top to bottom and then traced back from bottom to top. Thus, the solution is to have f(n) = f(n-1) + f(n-2) implemented from bottom to top.

This bottom-top implementation applies the algorithm called Dynamic Programming. Here is the formulation for dp:

The space complexity of the above implementation is O(n), but this can be reduced to O(1) by maintaining the values of count[i-1] and count[i-2] only.

## II. Decode ways

91. Decode Ways: determine the total number of ways to decode an encoded message which contains digits only; a message is encoded by converting letters to numbers using this mapping ‘A’ -> 1, …, ‘Z’ -> 26.

It is easy to apply the backtracking algorithm to this problem. For a digit in the message, it can be decoded to a letter; or it can combine the digit next to it and then be decoded to a new letter. Thus, we have two choices when we handle message[i]. We can try the first choice and then try the second one when it backtracks.

It is a solution of brutal force with pruning. The time complexity is O(2^n), supposing the length of the message is n. How can we optimize this solution by applying dynamic programming?

First, introduce memorization: let count[i] be the number of decode ways for message.substring(i). It is because in the backtracking implementation countWays(i, message, len) is called for more than once for the same i, which can be avoided by memorization.
Second, have it implemented from bottom to top: calculate count[i] in the order that i descends from len-1 to 0.

Thus, we have the formulation for dp:

Note that this formulation looks a lot like the implementation in the countWays function. Actually, the thinking process is similar, so it shouldn’t hard to come up with a dp solution from brutal force.

Because count[i] depends on count[i+1] and count[i+2] only, we don’t need to maintain an array for storing all the intermediate results.

## III. Paint house

There are a row of n houses, each house can be painted with one of the k colors.
The cost of painting each house with a certain color is different.
You have to paint all the houses such that no two adjacent houses have the same color.
The cost of painting each house with a certain color is represented by a n*k cost costs.
For example, costs is the cost of painting house 0 with color 0; costsis the cost of painting house 1 with color 2, and so on…
Find the minimum cost to paint all houses.

Here is an implementation of brutal force that applies backtracking. It is quite straightforward, so it is easy to come up with.

How can we optimize this solution? Let’s first locate where the double counting is in the above implmentation.
Suppose there are 5 houses and 4 colors. If we paint house 0 with color 1, we are going to paint house 1 using colors except color 1, we will call the paint function like this:

If we paint hourse 0 with color 3, we are going to paint house 1 using colors except color 3, we will call the paint function like this (and most of them are duplicates):

Thus, we need to memorize the mediate results to avoid double counting. We can adopt the bottom-up idea - the minimum cost of house i using color j depends on the minimum cost of house i+1 using colors except color j, so we have the formulation as follows:

The time complexity for this implementation is O(n * k * k).

Follow-up: can we solve it in O(n * k)?
The answer is yes. It is unnecessary to search the k cost value for house i+1 to get the minimum cost. Since all we need is the minimum result from a previous loop for i+1, why not just keep the minimum result? The minimum result is not valid if house i+1 use color j to get the minimum result and we want to try the same color for house i. But we can keep the most two smallest costs instead of one, and use the second smallest cost as the minimum result if house i and house i+1 use the same color.

## Summary

It’s ok that we can only come up with a brutal-force solution at first. Write it down, and look for double counting. Then we can introduce memorization for intermediate results to avoid repetition works. Last but not the least, memorization requires the intermediate results are calculated from bottom to top.
If you compare the implementations of both solutions, they are essentially the same, but dynamic programming introduces memorization and bottom-up implementation for optimization.