276. Paint Fence

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

You are painting a fence of n posts with k different colors. You must paint the posts following these rules:

Every post must be painted exactly one color. There cannot be three or more consecutive posts with the same color. Given the two integers n and k, return the number of ways you can paint the fence.

Example 1:

Input: n = 3, k = 2
Output: 6

Explanation: All the possibilities are shown. Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.

Example 2:

Input: n = 1, k = 1
Output: 1

Example 3:

Input: n = 7, k = 2
Output: 42

Code

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

class Solution:
    def numWays(self, n: int, k: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return k
        if n == 2:
            return k * k
        dp = [0] * n
        dp[0] = k
        dp[1] = k * k

        for i in range(2, n):
            # 涂上和之前第一个post不同的颜色
            # 涂上和之前第二个post不同的颜色
            dp[i] = dp[i - 1] * (k - 1) + dp[i - 2] * (k - 1)

        return dp[n - 1]