There's a problem in Kleinberg & Tardos's Algorithm Design (Chapter 6, Question 4) where you are running a lightweight consulting business that has two offices: NYC and SF. In month $i$, you'll incur an operating cost of $N(i)$ if you run the business out of NY; you'll incur an operating cost of $S(i)$ if you run the business out of SF. There is a moving cost $M$ if you decide to switch offices. The goal is to minimize total cost. According to the solutions, a DP solution would look like this:

$$ OPT(i, N) = N(i) + \min(OPT(i-1, N), OPT(i-1, S) + M), \\ OPT(i, S) = S(i) + \min(OPT(i-1, S), OPT(i-1, N) + M). $$

I'm trying to figure out how one can use recursion as opposed to DP to solve this solution. My understanding is that recursion works from top to bottom and DP works bottom up. I'm just having trouble actually figuring out a viable top to bottom recursive algorithm would look like in this case.


The recursive solution is to use the recurrence directly.

It corresponds to the following algorithm:

Function OPT(i, site):
    If i = 0, return 0
    If i > 0 and site = N, return N(i) + min(OPT(i-1, N), OPT(i-1, S) + M)
    If i > 0 and site = S, return S(i) + min(OPT(i-1, S), OPT(i-1, N) + M)

If you run this algorithm using memoization (not recomputing the value for the same input), then you get essentially the dynamic programming solution.

One way to implement this kind of approach is like so:

Function OPTm(i, site):
    If i = 0, return 0
    If (i, site) in Database, return Database(i, site)
    If site = N, answer = N(i) + min(OPTm(i-1, N), OPTm(i-1, S) + M)
    If site = S, answer = S(i) + min(OPTm(i-1, S), OPTm(i-1, N) + M)
    Database(i, site) = answer
    return answer

Yuval's answer shows you how to write a recursive solution.

Here I would like to correct a misunderstanding about dynamic programming in the question that is pretty common.

Although the majority code in programming language that applies dynamic programming uses bottom-up table-filling method, dynamic programming is not bottom up only.

In fact, the thinking phase of dynamic programming is done overwhelming in recursive way. That is, figuring out what are the smaller problems that could contribute and determine the given final or larger problems as well as finding the recurrence relations.

In fact, even if the programming code is written as a recursive solution, that code is still called dynamic programming.

More information can be found in the Wikipedia entry.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy