LeetCode Q276: 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.

Solution:

Using DP. To know how many ways to paint current house, we need to know two things. First, the total number of ways to paint previous houses. Second, We need to know whether the house in the last round is paint the color as same as the house before it.

So, we can create a Nx2 array to same the total number of ways to paint current n houses for first the current house is paint differently with previous one and second the current house is paint the same color as previous one.

To further optimize the code, could just use two variable to save results.

	class Solution {
	public:
	int numWays(int n, int k) {
	if(n<=1||k<=0)
	return n==0? 0:k;
	vector<vector<int> > N(n+1, vector<int> (2, 0));
	N[0][0]=k; N[0][1]=1;
	N[1][0]=N[0][0]*(k-1); N[1][1]=N[0][0];
	for(int i=2; i<n; i++){
	int v00 = N[i-1][0]*(k-1); // not same, not same
	int v01 = N[i-1][0]; // not same, same
	int v10 = N[i-1][1]*(k-1); // same, not same
	N[i][0] = v00+v10;
	N[i][1] = v01;
	}
	return N[n-1][0] + N[n-1][1];
	}
	};

view raw Q276.cpp hosted with ❤ by GitHub

Round 2 solution:
For the first post, there is total k ways to paint it. For the second post, if it is paint differently than first one, there is (k-1)*k ways, it is paint in a same way, there is k. Starting from the 3rd post, if paint differently, we add up the case where first if previous one was paint differently, second if previous one is paint same.

	class Solution {
	public:
	int numWays(int n, int k) {
	if(n==0||k<=0)
	return 0;
	int pre[2] = {k, 0};
	for(int i=1; i<n; i++){
	int notSame = pre[0]*(k-1)+pre[1]*(k-1);
	int same = pre[0];
	pre[0]=notSame;
	pre[1]=same;
	}
	return pre[0]+pre[1];
	}
	};

view raw Q276Rnd2.cpp hosted with ❤ by GitHub