Paint Fence

https://leetcode.com/problems/paint-fence/description/

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.

Thoughts

https://discuss.leetcode.com/topic/23426/o-n-time-java-solution-o-1-space/2?page=1

看到问多少种先想到DP. 到第i个post一共能有多少种方法取决于它和前面是不是同一种颜色. 因此想到要用两种状态. sameCount表示到i时, 它与前面是同一种颜色, 一共能有多少种; diffCount表示它与前面不同时能有多少种. 由于最多只能有两个连着的相同, 因此sameCount的值等于上一块diffCount的值.

Code

class Solution {
public:
    int numWays(int n, int k) {
        if (n == 0) return 0;
        if (n == 1) return k;
        int same_cnt = k, diff_cnt = k * (k - 1);
        for (int i = 3; i <= n; ++i) {
            int tmp = diff_cnt;
            diff_cnt = (same_cnt + diff_cnt) * (k - 1);
            same_cnt = tmp;
        }
        return same_cnt + diff_cnt;
    }
};

class Solution {
    public int numWays(int n, int k) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return k;
        }
        int diffCount = k * (k - 1);
        int sameCount = k;
        for (int i = 3; i <= n; i++) {
            int tmp = diffCount;
            diffCount = diffCount * (k - 1) + sameCount * (k - 1);
            sameCount = tmp;
        }
        return diffCount + sameCount;
    }
}

Analysis

时间复杂度O(N).