Open Shawngbk opened 7 years ago
则主要思想是，如果前两根栅栏颜色相同，则第三根栅栏的颜色不能跟前两根的栅栏颜色相同，若是前两根栅栏颜色不同，则第三根栅栏颜色随便涂。综合的思想就是，第三根栅栏或者与第一根栅栏的颜色不同，或者与第二根的栅栏颜色不同。（即，包括了，可以与前两个栅栏的颜色都不同，与第一根栅栏颜色不同时，可以与第二根相同，与第二根栅栏不同的时候可以与第一根相同）。 题意说的是不能有超过连续两个相同的颜色, 也就是说最多有两个相邻柱子染同样颜色.
所以在染一个柱子的时候, 要考虑是否和上一个柱子颜色相同.
如果和上一个相同的话那么上一个有多少种和上上次不同的染色方案, 那么当前柱子也有多少种染色方案.
如果和上一个不同的话那么染色方案就为(k-1)*(之前总共多少染色方案).
public class Solution { public int numWays(int n, int k) { int[] same = new int[n]; int[] dif = new int[n]; if(n == 0 || k == 0) return 0; if(n == 1) return k; same[0] = same[1] = k; dif[1] = k(k-1); for(int i = 2; i < n; i++) { same[i] = dif[i-1]; //第i个必须与前面不同，就是与第i－1不同或者与i－2不同，不能有连续三个相同 dif[i] = (k-1)same[i-1] + (k-1)*dif[i-1]; } return same[n-1] + dif[n-1]; } }
google
Shawngbk
commented
7 years ago Shawngbk
commented
7 years ago
则主要思想是，如果前两根栅栏颜色相同，则第三根栅栏的颜色不能跟前两根的栅栏颜色相同，若是前两根栅栏颜色不同，则第三根栅栏颜色随便涂。综合的思想就是，第三根栅栏或者与第一根栅栏的颜色不同，或者与第二根的栅栏颜色不同。（即，包括了，可以与前两个栅栏的颜色都不同，与第一根栅栏颜色不同时，可以与第二根相同，与第二根栅栏不同的时候可以与第一根相同）。 题意说的是不能有超过连续两个相同的颜色, 也就是说最多有两个相邻柱子染同样颜色.
所以在染一个柱子的时候, 要考虑是否和上一个柱子颜色相同.
如果和上一个相同的话那么上一个有多少种和上上次不同的染色方案, 那么当前柱子也有多少种染色方案.
如果和上一个不同的话那么染色方案就为(k-1)*(之前总共多少染色方案).
public class Solution { public int numWays(int n, int k) { int[] same = new int[n]; int[] dif = new int[n]; if(n == 0 || k == 0) return 0; if(n == 1) return k; same[0] = same[1] = k; dif[1] = k(k-1); for(int i = 2; i < n; i++) { same[i] = dif[i-1]; //第i个必须与前面不同，就是与第i－1不同或者与i－2不同，不能有连续三个相同 dif[i] = (k-1)same[i-1] + (k-1)*dif[i-1]; } return same[n-1] + dif[n-1]; } }