FXTi's blog
0%

paint-fence

Posted on Edited on

Paint Fence – LeetCode 276

Problem

Description

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.

Answer

Original

Code

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

思路

根据题意可以有两个连续的重复，那么第三个就不能和前两个相同，于是就是前两个的k-1倍。于是有$dp[3] = (k - 1) \times dp[1] + (k - 1) \times dp[2]$。时间复杂度$O(n)$，空间复杂度$O(1)$。

Better

思路

还没看到更好的思路。