The first one is DP. We define dp[n][0] as the number of all valid combination with the last two posts painted in different colors (post[n] != post[n-1]), and, dp[n][1] as the number of all valid combination with the last two posts painted in the same color (and of course, post[n-2] is painted in different color with post[n-1], in other word, post[n] == post[n-1] != post[n-2]). It is obvious that the total number of valid combination is dp[n][0] + dp[n][1].

How to calculate dp[n] from dp[n-1]? To get dp[n][0], we just need to pick a color for post[n] that is different from post[n-1]. There are totally (k-1) options for a given color of post[n-1]. To get dp[n][1], the only way is to pick a color for post[n] that is the same as post[n-1]. So, dp[n][0] = (k-1) * (dp[n-1][0] + dp[n-1][1]); dp[n][1] = dp[n-1][0].

The code is pretty straight forward:

```
public int numWays(int n, int k) {
if (n == 0 || k == 0) return 0;
int[][] dp = new int[n + 1][2];
dp[1][0] = k;
for (int i = 2; i <= n; i++) {
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) * (k - 1);
dp[i][1] = dp[i - 1][0];
}
return dp[n][0] + dp[n][1];
}
```

As we can see only dp[i-1] is used to calculate dp[i], there is no need to keep dp[i-2], dp[i-3] ...

So, the code can be simplified:

```
public int numWays(int n, int k) {
if (n == 0) return 0;
int one = k, two = 0;
for(int i = 1; i < n; i++) {
one = (two + (two = one)) * (k-1);
}
return one + two;
}
```

The second solution is basically the same as above except using O(0) space.

The third try is matrix multiplication. If we exam the above DP carefully, we can tell:

dp[n] = dp[n-1] * {{k-1, 1}, {k-1, 0}} = dp[n-2] * {{k-1, 1}, {k-1, 0}} * {{k-1, 1}, {k-1, 0}} = .... // matrix multiplication

So, dp[n] = dp[1] * ({{k-1, 1}, {k-1, 0}} ^ (n-1)). Fortunately, we have a way to calculate the power of a matrix in O(lg(n)) runtime where n is the power.

```
public int numWays(int n, int k) {
if (n == 0 || k == 0) return 0;
int[][] next = {{k - 1, 1}, {k - 1, 0}};
int[][] pow = pow(next, n - 1);
return k * (pow[0][0] + pow[0][1]);
}
private int[][] pow(int[][] matrix, int n) {
int[][] ans = {{1, 0}, {0, 1}};
while (n > 0) {
if ((n & 1) == 1) {
ans = multiplication(ans, matrix);
}
matrix = multiplication(matrix, matrix);
n >>= 1;
}
return ans;
}
private int[][] multiplication(int[][] m1, int[][] m2) {
int[][] ans = new int[2][2];
ans[0][0] = m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0];
ans[0][1] = m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1];
ans[1][0] = m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0];
ans[1][1] = m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1];
return ans;
}
```

In theory, the third solution is O(lg(n)), but since the test case is pretty small, you don't really see the benefits.