Paint Fence
这个居然是easy题…这个dp真的有点难难度. 首先观察第i个可涂的颜色, 可以涂和i-1一样, 也可以不一样, 一样是k-1个涂法, 不一样呢? 不一样的话, 因为不能三个连续一样, 那么如果和前边一个不一样, 就要保证前边两个是一样的, 换句话说, 就是和i-2的不一样, 那么也是k-1个….这个很难想到..
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;
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] * (k - 1); // numbers of same ways for i pos
dp[i] += dp[i-2] * (k - 1); // numbers of diff ways for i pos
}
return dp[n];
}
}