276. Paint Fence

Question:

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.

Thinking:

  • Method 1:
    • 动态规划。
      • 当n为0时，结果为0。
      • 当n为1时结果为K。
      • 当n > 1时
        • 与前一个不同 dp[i - 1] * (k - 1)
        • 与前一个相同(则与前前一个不同) dp[i - 1] - dp[i - 2]
        • 综上所述结果为 dp[i - 1] * k - dp[i - 2]
	private static int paintFence(int n, int k){
		int[] dp = new int[n + 1];
		dp[0] = 0; dp[1] = k;
		for(int i = 2; i <= n; i++){
			dp[i] = dp[i - 1] * k - dp[i - 2];
		}
		return dp[n];
	}

Second time

  1. Original values:
    • 0: 0 and 1: K
    • for each index, there are two terms
      • dp[i - 1] * (k - 1) (Not consider previous two are the same)
      • dp[i - 2] (Previous two are the same)
      • dp[i] = dp[i - 1] * (k - 1) - dp[i - 2] 
         private static int paintFence(int n, int k){
  int[] dp = new int[n + 1];
  dp[0] = 0; dp[1] = k;
  for(int i = 2; i <= n; i++){
  dp[i] = dp[i - 1] * k - dp[i - 2];
  }
  return dp[n];
 }