Thinking process

Starting from the simplest example

• n = 3, k = 2
• n = 4, k = 3
• n = 4, k = 5

Try to find the pattern

• for the post i, its color depends on either the color of post i - 1 or the color of post i - 2
• and no matter which it is, there are k - 1 choices

Mistakes

It's too difficult to use Combinatorics

s

public class Solution {
    public int numWays(int n, int k) {
        if (n == 0 || k == 0) return 0;
        if (n == 1) return k;
        if (k == 1 && n >= 3) return 0;

        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = k;
        dp[2] = k * k;

        if (n <= 2) return dp[n];

        for (int i = 3; i <= n; i++) {
            dp[i] = (k - 1) * (dp[i - 1] + dp[i - 2]);
        }

        return dp[n];
    }
}

Making use of Rolling Array to reduce space use

public class Solution {
    public int numWays(int n, int k) {
        if (n == 0 || k == 0) return 0;
        if (n == 1) return k;
        if (k == 1 && n >= 3) return 0;

        int[] dp = {0, k, k * k};

        if (n <= 2) return dp[n];

        for (int i = 3; i <= n; i++) {
            dp[i % 3] = (k - 1) * (dp[(i - 1) % 3] + dp[(i - 2) % 3]);
        }

        return dp[n % 3];
    }
}