# 276. Paint Fence

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: int numWays(int n, int k) { if (n == 0) return 0; if (n == 1) return k; if (n == 2) return k * k; // dp[i] := # of ways to paint n posts with k colors vector dp(n + 1); dp[0] = 0; dp[1] = k; dp[2] = k * k; for (int i = 3; i <= n; ++i) dp[i] = (dp[i - 1] + dp[i - 2]) * (k - 1); return dp[n]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public int numWays(int n, int k) { if (n == 0) return 0; if (n == 1) return k; if (n == 2) return k * k; // dp[i] := # of ways to paint n posts with k colors int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = k; dp[2] = k * k; for (int i = 3; i <= n; ++i) dp[i] = (dp[i - 1] + dp[i - 2]) * (k - 1); return dp[n]; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution: def numWays(self, n: int, k: int) -> int: if n == 0: return 0 if n == 1: return k if n == 2: return k * k # dp[i] := # of ways to pan posts with k colors dp = [0] * (n + 1) dp[0] = 0 dp[1] = k dp[2] = k * k for i in range(3, n + 1): dp[i] = (dp[i - 1] + dp[i - 2]) * (k - 1) return dp[n]