276. Paint Fence

When there is only one fence, we have total k ways to paint.
When there is two fence, for the second fence, we can paint the same color with the first one and the total ways to paint these two posts is k. OR we can paint the different color and the total ways to paint these two posts is k*(k-1). If we can keep the total ways to paint ith post, then the ways for ith post is
Case 1: i-1 and i-2 have the same color, then the ways to paint is (k-1) * dp[i-2]
Case 2: i-1 and i-2 have different colors, then the ways to paint is (k-1) * dp[i-1]
So the dp[i] = (dp[i-2] + dp[i-1])*(k-1);

1:  class Solution {  
2:  public:  
3:    int numWays(int n, int k) {  
4:      if (n == 0) return 0;  
5:      if (n == 1) return k;  
6:      vector<int> dp(n, 0);  
7:      dp[0] = k;  
8:      dp[1] = k+k*(k-1);  
9:      for (int i = 2; i < n; i++) {  
10:        dp[i] = (dp[i-1] + dp[i-2]) * (k-1);  
11:      }  
12:      return dp[n-1];  
13:    }  
14:  };  

Also, this DP solution can be optimized to have O(1) space because we only care about previous two states.

1:  class Solution {  
2:  public:  
3:    int numWays(int n, int k) {  
4:      if (n == 0) return 0;  
5:      if (n == 1) return k;  
6:      int n_2 = k, n_1 = k*(k-1);  
7:      for (int i = 2; i < n; i++) {  
8:        int tmp = n_1;  
9:        n_1 = (n_2 + n_1) * (k-1);  
10:        n_2 = tmp;  
11:      }  
12:      return n_2 + n_1;  
13:    }  
14:  };