Question

Formatted question description: https://leetcode.ca/all/276.html

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 <= 10⁵
The testcases are generated such that the answer is in the range [0, 2³¹ - 1] for the given n and k.

Algorithm

If either n == 0 or k == 0, then it is impossible to paint the fence according to the requirement, so return 0.

Use dynamic programming. Create a 2D array dp with n rows and 2 columns, where

dp[i][1] represents the number of ways to paint the fence’s first i + 1 posts while the i-th post has the same color as its previous post,
and dp[i][0] represents the number of ways to paint the fence’s first i + 1 posts while the i-th post doesn’t have the same color as its previous post.

Obviously, dp[0][0] = 0 and dp[0][1] = k. For i > 0, dp[i][0] = dp[i - 1][1] since the current post has the same color as the previous post, and dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) * (k - 1) since to select a color different to the previous post, there are k - 1 selections.

Finally, return dp[n - 1][0] + dp[n - 1][1].

Code

public class Paint_Fence {

    public static void main(String[] args) {
        Paint_Fence out = new Paint_Fence();

        Solution s1 = out.new Solution();
        Solution_noArray s2 = out.new Solution_noArray();

        System.out.println(s1.numWays(3, 2)); // 6
        System.out.println(s2.numWays(3, 2));
    }

    class Solution {
        public int numWays(int n, int k) {
            if (n == 0 || k == 0)
                return 0;

            // `dp[i][0]` same color
            // `dp[i][1]` different color
            int[][] dp = new int[n][2];
            dp[0][0] = 0;
            dp[0][1] = k;
            for (int i = 1; i < n; i++) {
                dp[i][0] = dp[i - 1][1]; // or else 3-posts the same color
                dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) * (k - 1);
            }
            return dp[n - 1][0] + dp[n - 1][1];
        }
    }

    public class Solution_noArray {
        public int numWays(int n, int k) {
            if (n == 0) return 0;
            int same = 0, diff = k;
            for (int i = 2; i <= n; ++i) {
                int t = diff;
                diff = (same + diff) * (k - 1);
                same = t;
            }
            return same + diff;
        }
    }
}

############

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

// OJ: https://leetcode.com/problems/paint-fence/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int numWays(int n, int k) {
        if (k == 1 && n >= 3) return 0;
        int dp[2] = {k, 0};
        for (int i = 1; i < n; ++i) {
            int next[2] = {(k - 1) * (dp[0] + dp[1]), dp[0]};
            swap(next, dp);
        }
        return dp[0] + dp[1];
    }
};

class Solution:
    def numWays(self, n: int, k: int) -> int:
        # `dp[i][0]` same color
        # `dp[i][1]` different color
        dp = [[0] * 2 for _ in range(n)]
        dp[0][1] = k
        for i in range(1, n):
            dp[i][0] = dp[i - 1][1] # same as previous, or else 3-posts the same color
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) * (k - 1) # not the same as previous
        return sum(dp[-1])

############

class Solution(object):
  def numWays(self, n, k):
    """
    :type n: int
    :type k: int
    :rtype: int
    """
    if n > 2 and k == 1:
      return 0
    if n < 2:
      return n * k
    pre = k * k
    ppre = k
    for i in range(2, n):
      tmp = pre
      pre = (k - 1) * (pre + ppre)
      ppre = tmp
    return pre

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

276 - Paint Fence

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions