有一个有n个帖子的围栏,每个帖子都可以涂上一种k颜色。您必须绘制所有帖子,使得不超过两个相邻的栅栏柱具有相同的颜色。返回可以绘制栅栏的总方式。
diff - 不同颜色的组合数, 相同 - 具有相同颜色的组合数量, n - 帖子数量, k - 颜色数量。
对于n = 1:
diff = k;
same = 0;
对于n = 2:
diff = k * (k - 1);
same = k;
对于n = 3:
diff = (k + k * (k - 1)) * (k - 1);
same = k * (k - 1);
最后的公式是:
diff[i] = (diff[i - 1] + diff[i - 2]) * (k - 1);
same[i] = diff[i - 1];
我理解如何找到same[i]
,但我不明白如何找到diff[i]
。你能解释一下diff[i]
的公式吗?
total[i] = diff[i] + same[i] (definition)
diff[i] = (k - 1) * total[i-1]
= (k - 1) * (diff[i-1] + same[i-1])
= (k - 1) * (diff[i-1] + diff[i-2])
这是组合论的论点。
让diff[i, c]
根据问题陈述的规则绘制i
帖子的方式的数量,以便最后的围栏涂上颜色c
。
我们有:
diff[i, c] = diff[i - 1, c'] + diff[i - 2, c''], c' != c OR c'' != c
对于我们绘制c
的每个i
,前者可以以c' != c
结束(在这种情况下我们不关心第二个先前是什么),或者第二个之前可以以c'' != c
结束(在这种情况下我们不会关心以前是什么),或两者兼而有之。
对于k - 1
,c' != c
和k - 1
有c'' != c
可能性。所以我们可以从复发中删除c
并简单地写:
diff[i] = (k - 1) * (diff[i - 1] + diff[i - 2])
这是你拥有的。
解决方案涉及详细解释。请看看。
public class PaintingFence {
public static int paintFence(int n, int k) {
//if there is 0 post then the ways to color it is 0.
if(n == 0) return 0;
//if there is one 1 post then the way to color it is k ways.
if(n == 1) return k;
/**
* Consider the first two post.
* case 1. When both post is of same color
* first post can be colored in k ways.
* second post has to be colored by same color.
* So the way in which the first post can be colored with same color is k * 1.
*
* case 2. When both post is of diff color
* first post can be colored in k ways.
* second post can be colored in k-1 ways.
* Hence the ways to color two post different is k * (k - 1)
*/
int same = k * 1;
int diff = k * (k -1);
/**
* As first 2 posts are already discussed, we will start with the third post.
*
* If the first two post are same then to make the third post different, we have
* k-1 ways. Hence same * (k-1)
* [same=k, so same * k-1 = k*(k-1) = diff => Remember this.]
*
* If the first two posts are different then to make the third different, we also have
* k - 1 ways. Hence diff * (k-1)
*
* So to make third post different color, we have
* same * (k-1) + diff * (k-1)
* = (same + diff) * (k-1)
* = k-1 * (same + diff)
*/
for(int i=3;i <=n; i++) {
int prevDiff = diff;
diff = (same + diff) * (k - 1); //as stated above
/**
* to make the third color same, we cannot do that because of constraint that only two
* posts can be of same color. So in this case, we cannot have to same color so it has to be
* diff.
*/
same = prevDiff * 1;
}
return same + diff;
}
public static void main(String[] args) {
System.out.println(paintFence(2, 4));
System.out.println(paintFence(3, 2));
}
}