# Easy to understand Java O(n) runtime, O(1) space

• w(n) number of ways to paint n posts

p(n) color of the nth post

w(n) consists of two cases:

1.p(n) == p(n - 1)

2.p(n) != p(n - 1)

case 2 is easy. for every way of painting all previous (n - 1) posts, you have (k - 1) ways to paint p(n)
because you can choose k - 1 different color rather than the same color as p(n - 1)

so w(n - 1) * (k - 1)

notice that for p(n) == p(n - 1), p(n - 1) must be not equal to p(n - 2), this is equalvalent to replace n by n - 1
for the formular above, essentially the same as case2 but for a smaller n.
so w(n - 1 - 1) * (k - 1)

so w(n) = (k - 1) * (w(n - 1) + w(n - 2))

``````public class Solution {
public int numWays(int n, int k) {
if ((n == 0 || k == 0) || (k == 1 && n >= 3))
return 0;
int w1 = k;
int w2 = k * k;
int w3;
if (n == 1)
return w1;
if (n == 2)
return w2;
for (int i = 0; i <= n - 3; i++) {
w3 = (k - 1) * (w2 + w1);
w1 = w2;
w2 = w3;
}
return w2; // wrong if you return w3, w3 may not be initialized.
}
}``````

• I pretty had the same approach and ended up converting your code to python — returning w3 is perfectly fine. it's always initialized.

``````class Solution(object):
def numWays(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
if n == 0 or k == 0 or (k == 1 and n >= 3):
return 0

w1 = k
w2 = k*k;
if n == 1:
return w1
if n == 2:
return w2
w3 = 0
for i in range(3, n+1):
w3 = (k-1)*(w1 + w2)
w1 = w2
w2 = w3
return w3``````

• Great solution, and concise, clear explanation.

• @xuyirui Neat explanation -- thank you.
I'm not fully clear about the num_ways for case 1.

Case 2: w(n) = w(n-1) * (k-1)
Case1:
p(n) == p(n-1) && p(n-1) != p(n-2)

therefore, w(n) = w(n-1) * k // we can use k colors for n, multiplied by ways for n-1.
since we know p(n-1) != p(n-2), we reduce this to
w(n) = w(n-1-1) * (k-1) * k
w(n) = w(n-2) * (k-1) * k.

To summarize, i guess i couldn't understand case 1, where w(n) is just w(n-2) * (k-1) and not w(n-2) * (k-1) * k.

Update:
I think I see where I went wrong. keeping the post as is and updating, incase someone else made the same mistake.

therefore, w(n) = w(n-1) * k // we can use k colors for n, multiplied by ways for n-1.

This should be w(n) = w(n-1) * 1 // since we are painting `n` with the same color as `n-1`, essentially `1` choice and not `k` choices here.

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