Question

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

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])

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];
  }
}

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];
  }
};

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]
}