leetcode解题: Paint Fence (276)

发表于 | 分类于

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.

解法1: DP with O(N) time and O(1) space

经典DP, dp[i]表示第i根柱子可能paint的方法数量。考虑三根柱子，如果第i根柱子和第i - 1根一样，那么一定和第i-2根不一样，所以这种情况有k - 1个颜色可选。同理，如果i和第i -2根一样，
那必然和第i - 1根不一样，也是k - 1种颜色可选。
dp[i] = (k - 1) * (dp[i -1] + dp[i - 2])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int numWays(int n, int k) {
	
	if (n <= 0) {
		return 0; // If no fence exists, there is no way to paint it.
	}
	
	// Corner case 
	if (n == 1) {
		return k;
	}
	int[] dp = new int[]{k, k * k, k * k}; // initial value of dp[2] is set to be equal to dp[1]. 
	for (int i = 3; i <= n; i++) {
		dp[2] = (k - 1) * (dp[0] + dp[1]);
		dp[0] = dp[1];
		dp[1] = dp[2];
	}
	
	return dp[2];
        
}