Welcome to Subscribe On Youtube

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 <= 105
  • The testcases are generated such that the answer is in the range [0, 231 - 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]
    }
    

All Problems

All Solutions