How to convert this top down solution to bottom up solution?

Question

There is a fence with n posts, each post can be painted with one of the k colors. You have to paint all the posts such that no more than two adjacent fence posts have the same color. Return the total number of ways you can paint the fence.

I came up with the below Top Down solution for the above problem.

class Solution:

    def numWays(self, n, k):
        return self.numWaysHelper(n, k, -1, {})


    def numWaysHelper(self, n, k, i, dp):
        if n == 0:
            return 1
        if n < 0:
            return 0
        if (n,k) in dp:
            return dp[(n,k)]
        ways = 0
        for j in range(0, k):
            if i!=j:
                ways += self.numWaysHelper(n - 1, k, j, dp) + self.numWaysHelper(n - 2, k, j, dp)
        dp[(n,k)] = ways
        return ways

I am able to convert some other top down solutions to bottom up solutions. I wonder how to approach for the Bottom up solution for this? Is there anyway tips for in converting this top down to bottom solution?

Answer 1

Without reading your question:

From your code:

• slight remark, dp naming is used instead of memo (aka memoization)
• it is also misleading because k never changes during recursion (and this is important) (so no need to use k for dp)
• you are recurring with the couple (n, i) so instead it should be dp[n,i]

Now this becomes straightforward:

• build dp for n = 0, all i
• build dp for n = 1, all i
• build dp for n = 2, all i by using previously dp[0,j] and dp[1, j] for j != i
• build dp for n = 3 idem with dp[1, j] and dp[2, j]

kind of like you would for Fibonacci

def dp_approach(max_n, k):
  # we start with [n=-1, n=0]
  [dp_minus_one, dp_minus_two] = [[0] * k, [1] * k]
  for n in range(1, max_n):
    v = [None] * k
    for j in range (0, k):
      #use all previous dp except j
      s = 0
      for jprev in range(0, k):
        if j != jprev:
          s += dp_minus_one[jprev] + dp_minus_two[jprev]
      v[j] = s
    dp_minus_one = dp_minus_two
    dp_minus_two = v

  return sum(dp_minus_two)+sum(dp_minus_one)

Let's do a bit better: Let's have a look at some output for dp_approach(_, 7):

  for n 1 [6, 6, 6, 6, 6, 6, 6]
  for n 2 [42, 42, 42, 42, 42, 42, 42]
  for n 3 [288, 288, 288, 288, 288, 288, 288]
  for n 4 [1980, 1980, 1980, 1980, 1980, 1980, 1980]
  for n 5 [13608, 13608, 13608, 13608, 13608, 13608, 13608]

Notice that we are storing useless values: we start with [0]*k and [1]*k, which means we will always store at every layer identical values (because of symetry). We can thus take advantage of that to avoid manipulating an array and just use a single value (since it is repeated in the array as illustrated).

When iterating on k, we do k iterations (...) but only consider k-1 sums (i!=j) so we just multiply by k-1.

def dp_approach_2(max_n, k):
  # we start with [n=-1, n=0]
  [dp_minus_one, dp_minus_two] = [0, 1]
  for n in range(1, max_n):
    s = (dp_minus_one + dp_minus_two) * (k-1)
    dp_minus_one = dp_minus_two
    dp_minus_two = s
  return (dp_minus_one + dp_minus_two)*(k)

---

Finally with a bit of math we can even just give out the formula (it is not that pertinent, more likely just for fun) recall the form

u_{n+1} = a * u_n + a * u_{n-1}

which is very like Fibonacci, but with a != 1

Keywords are linear homogenous recurrence

• u_n = Cr_1^n + Dr_2^n with r = +-(sqrt(a^2/4+a/2) + a/2)
• special constants according to u_0=0 and u_1=1: C = -D and C = 1/(2 sqrt(a^2/4+a/2))

import math
def explicit_comp(n, a):
  def u_n (n):
    k = a - 1
    sq = math.sqrt(k ** 2 / 4 + k)
    r_1 = sq + k / 2
    r_2 = -sq + k / 2
    return 1 / (2 * sq) * (r_1 ** n - r_2 ** n)
  u_minusone = u_n(n-1)
  u_minustwo = u_n(n)
  return (u_minusone + u_minustwo) * a

PS: I just reversed your code I don't know if your original algorithm solves the question!