# DP with python, O(n) time O(1) space. Straightforward explanation.

• This problem is not obvious to me (it is medium in my opinion). I spent quite some time, and came up an idea of dynamic programming approach. Let us use `p(n)` to denote the color of post n, use `w(n)` to denote the number of ways to paint post n, and use `r(n)` to denote the returned number of ways to paint n posts.

``````for n == 0, return 0 or 1 # Up to you;
for n == 1, return k;
for n == 2,
if p(2) == p(1), then r(n)=k,
because the two have the same color.
if p(2) != p(1), then r(n)=k(k-1)
because w(1)=k, w(2)=k-1.
for n >= 3,
r(n) = r(n,when p(n)==p(n-1)) + r(n,when p(n)!=p(n-1))
``````

When `p(n-1) == p(n)`, we require `p(n-2) != p(n-1)`. This is the same as if we are painting (n-1) posts and the last two posts have different colors, which means `same(n)=diff(n−1)`.

When `p(n-1) != p(n)`, we have `r(n−1)` ways to paint the first n-1 posts, and `k−1` ways to paint the n-th post. So `diff(n)=r(n−1)(k−1)`.

Note that `r(n−1)` is really just the sum of `same(n−1)` and `diff(n−1)`.

Code:

``````def paintFence(n, k):
if n == 0:
return 0
if n == 1:
return k
# Now n >= 2.
# Initialize same and diff as if n == 2
same = k
diff = k*(k-1)
for i in range(3,n+1):
r_prev = same + diff  # r(i-1)
same = diff           # same(i)=diff(i-1)
diff = r_prev*(k-1)
return same + diff
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.