这题有歧义啊。。说的是颜色相同的相邻数量不能超过2个，不是颜色相同的对数不能超过2个，我日了。
搞懂之后就不难了，动态规划。
每一次粉刷都有2种可能，和前一个颜色相同；和前一个颜色不同。
same[i] = diff[i-1]; diff[i] = (same[i-1]+diff[i-1]) * (k-1);
总和是same[n]+diff[n]..
然后，这种一维DP是不需要整个数组的，3个变量就够了，但是这么写更清楚。
public class Solution { public int numWays(int n, int k) { if(n == 0 || k == 0) return 0; if(n > 2 && k == 1) return 0; if(n == 1) return k; int[] same = new int[n]; int[] diff = new int[n]; same[0] = k; same[1] = k; diff[0] = k; diff[1] = diff[0]*(k-1); for(int i = 2; i < n; i++) { same[i] = diff[i-1]; diff[i] = (diff[i-1]+same[i-1])*(k-1); } return same[n-1] + diff[n-1]; } } --------
二刷。
还是动态规划，分情况。
same[i] = diff[i-1];
diff[i] = (k-1) * (diff[i-1] + same[i-1])这次改成单一变量。。
Time: O(n)
Space: O(1)public class Solution { public int numWays(int n, int k) { if (n == 0 || k == 0) return 0; if (n == 1) return k; if (n == 2) return k*k; int same = k; int diff = k*(k-1); // diff[i] = (k - 1) * (diff[i-1] + same[i-1]) // same[i] = diff[i-1] for (int i = 3; i < n + 1; i++) { int temp = (k - 1) * (diff + same); same = diff; diff = temp; } return diff + same; }} 三刷。
这个题还是挺有意思的。
一刷二刷的思路是。
对于第n个房子来说，分成2种情况：
1.和n-1的颜色一样. 2.和n-1的颜色不一样.前者是dp(n-1)种可能，颜色一样，n-1有多少种可能，n就有多少。
后者是可选颜色数k-1，因为不一样所以-1，乘以dp[n-1]的可能性。按照这个思路做的。
这次换了个思路，按照rob house的方法考虑。
三个连起来的房子不能颜色一样，那对于第n个房子来说：要么跟n-1的颜色不一样，要么跟n-2的颜色不一样，要么跟n-1 n-2的颜色都不一样。
(k-1)(dp[n-1]) + (k-1) dp[n-2] 跟1颜色不一样乘以跟2颜色不一样。。里面已经包含跟1跟2都不一样了。。
public class Solution { public int numWays(int n, int k) { if (n == 0 || k == 0) return 0; if (n == 1) return k; if (n == 2) return k*k; int[] dp = new int[3]; dp[0] = k; dp[1] = k*k; for (int i = 2; i < n; i++) { dp[i%3] = (dp[(i-2)%3] + dp[(i-1)%3]) * (k-1); } return dp[(n-1)%3]; }}