276 Paint Fence

276. Paint Fence

1. 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.

Note: n and k are non-negative integers.

2. Implementation

(1) Memoization

思路: base case是当n=1时，我们有k种颜色可用，当n = 2时，我们有k * k种颜色可用，当n >= 3时，

有两种情况:

1. 如果在第i个fence上，i - 1和i - 2用的是同一种颜色，那么我们在i位置上有k - 1种颜色可用，假设f(i)表示在第i个fence上总共的paint方式， 那么这种情况下总共的paint方式 (k - 1) * f(i - 1)

2. 如果第i - 1和第i - 2分别用不同的颜色，那么在i位置上我们仍然有 k - 1种颜色可用，只要和第i - 1个fence的颜色不同即可，这种情况下总共的paint方式有 (k - 1) * f(i - 2)

3. 综上，f(i) = (k - 1) * (f(i - 1) + f(i - 2))

第一种方法利用记忆化搜索，将第i个位置上可用的paint方式存在cache里

class Solution {
    public int numWays(int n, int k) {
        if (n == 0 || k == 0) {
            return 0;
        }

        int[] cache = new int[n + 1];
        return waysToPaintFence(n, k, cache);

    }

    public int waysToPaintFence(int n, int k, int[] cache) {
        if (cache[n] != 0) {
            return cache[n];
        }

        if (n == 1) {
            return k;
        }

        if (n == 2) {
            return k * k;
        }

        cache[n] = (k - 1) * (waysToPaintFence(n - 1, k, cache) + waysToPaintFence(n - 2, k, cache));
        return cache[n];
    }
}

(2) DP

思路由于已经推出状态转移方程，可以直接用DP做

class Solution {
    public int numWays(int n, int k) {
        if (n == 0 || k == 0) {
            return 0;
        }

        int[] ways = new int[n + 1];
        if (n == 1) {
            return k;
        }

        if (n == 2) {
            return k * k;
        }

        ways[1] = k;
        ways[2] = k * k;

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

3. Time & Space Complexity

Memoization:

DP: 时间复杂度O(n), 空间复杂度O(n)