How to identify it is a DP problem

Typically, all the problem that require to maximize or minimize the certain quality or counting problems can be solved by using Dynamic Programming.

Determine the recursive relationship

For each DP problem, we should find the optimal solution using previous computed solutions. I will illustrate how to determine the relationship and construct the recursive method in two problems.

Rod Cutting

We will use the Rod Cutting problem from the book.

Given a rod of length n inches and a table of prices \(p_i\) for \(i\) = 1, 2, ..., \(n\), determine the maximum revenue \(r_n\) obtainable by cutting up the rod and selling the pieces.

As book illustrated, we can determine the optimal solution with: \[ r_n = max_{1\le i\le n}(p_i+r_{n-i}) \] Then we can write the recursive code:

def Cut_Rod(p,n):
    if n == 0:
        return 0
    q = -1
    for i in range(1, n):
        q = max(q, p[i]+Cut_Rod(p, n-1))
    return q

House Robber

Another similar problem called House Robber from LeetCode:

House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Example:
Input: [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

We can determine this problem into following subproblem: \[ F(n)=max\{ F(n-2)+nums[n],F(n-1) \} \] Then, the recursive code is like this:

def rob(n, i):
    if (i < 0): return 0
    return max(rob(n, i-2)+n[i], rob(n, i-1))

Problem

The severe problem of using such problem is the computational performance. Each time we need to calculate the subproblem repeatedly. Therefore, it could result in the computational waste.

In the rob cut problem, the total time of applying such recursive approach is: \[ T(n)=1+\sum^{n-1}_{j=0}T(j) \] Through applying induction method, we can prove that \[ T(n)=2^n \] which is too costly in computation.

It would be better to reduce the redundant computation while executing the subproblems.

Memorization

Therefore, we could store the previous results into the array, and then use these pre-computed results in the latter computation.

We can three possible ways to memorize the results:

Recursive + Memorized List (top-down)
Iterative + Memorized List (bottom-up)
Iterative + variables (bottom-up)

Personally, I prefer the latter two methods (relatively faster in most occasions and save memory).

We will use these three methods to solve House Robber problem.

Recursive Method

# n is the list of input
def rob(n):
    # memo list r
    r = [-1] * len(n)
    return rob(n, r, len(n)-1)

def rob(n, r, i):
    if (i < 0): 
        return 0
    if (r[i] < 0):
        r[i] = max(rob(n, i-2) + n[i], rob(n, i-1))
    return r[i]

Iterative Method with Memo List

# n is the list of input
def rob(n):
    memo = []
    memo[0] = 0
    memo[1] = n[0]
    for i in range(1, len(n)):
        memo[i+1] = max(memo[i], memo[i-1] + nums[i])
    return memo[size(n)]

Iterative Method with Variables

Since every step, we only use \(memo[i]\) and \(memo[i-1]\), so we can store these two values into two variables.

# n is the list of input
def rob(n): 
    if len(n) == 0: 
        return 0
    prev1 = 0, prev2 = 0
    for i in n:
        prev2 = prev1
        prev1 = max(prev2 + i, prev1)
    return prev1

Reference

[1] [https://leetcode.com/problems/house-robber/discuss/156523/From-good-to-great.-How-to-approach-most-of-DP-problems.](https://leetcode.com/problems/house-robber/discuss/156523/From-good-to-great.-How-to-approach-most-of-DP-problems.)

algorithm