276. Paint Fence

Description

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

 

Constraints:

  • 1 <= n <= 50
  • 1 <= k <= 105
  • The testcases are generated such that the answer is in the range [0, 231 - 1] for the given n and k.

Solutions

Solution 1

Python Code
1
2
3
4
5
6
7
8

class Solution:
    def numWays(self, n: int, k: int) -> int:
        dp = [[0] * 2 for _ in range(n)]
        dp[0][0] = k
        for i in range(1, n):
            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) * (k - 1)
            dp[i][1] = dp[i - 1][0]
        return sum(dp[-1])

Java Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

C++ Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

Go Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func numWays(n int, k int) int {
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, 2)
	}
	dp[0][0] = k
	for i := 1; i < n; i++ {
		dp[i][0] = (dp[i-1][0] + dp[i-1][1]) * (k - 1)
		dp[i][1] = dp[i-1][0]
	}
	return dp[n-1][0] + dp[n-1][1]
}