Welcome to Subscribe On Youtube

Question

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

 276	Paint Fence

 There is a fence with n posts, each post can be painted with one of the k colors.

 You have to paint all the posts such that no more than two adjacent fence posts have the same color.

 Return the total number of ways you can paint the fence.

 Note:
 n and k are non-negative integers.

 @tag-dp

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

Java

• Java
• C++
• Python

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

• // 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 = [[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(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
  
  

All Problems

All Solutions