Paint Fence
这个居然是easy题…这个dp真的有点难难度. 首先观察第i个可涂的颜色, 可以涂和i-1一样, 也可以不一样, 一样是k-1个涂法, 不一样呢? 不一样的话, 因为不能三个连续一样, 那么如果和前边一个不一样, 就要保证前边两个是一样的, 换句话说, 就是和i-2的不一样, 那么也是k-1个….这个很难想到..
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
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]; } } |