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

Solution

题目有点描述不清，其实就是要保证最多两个相邻的fence同色。用DP解即可。

DP, time O(n), space O(1)

dp[i][0] means same with prev color, dp[i][1] means diff from prev color

• dp[0][0] = 0, dp[0][1] = k
• dp[i + 1][0] = dp[i][1]
• dp[i + 1][1] = (dp[i][0] + dp[i][1]) * (k - 1)

return dp[n - 1][0] + dp[n - 1][1]

class Solution {
    public int numWays(int n, int k) {
        if (n == 0 || k == 0) {
            return 0;
        }
        
        if (n == 1) {
            return k;
        }
        
        int sameWithPrev = 0;
        int diffWithPrev = k;
        
        for (int i = 1; i < n; ++i) {
            int tmp = sameWithPrev;
            sameWithPrev = diffWithPrev;
            diffWithPrev = (tmp + diffWithPrev) * (k - 1);
        }
        
        return sameWithPrev + diffWithPrev;
    }
}