Sector Coloration

Posted on | In | |

题目描述

圆盘染色问题

现将一个圆盘分成n个扇形，要求使用m种颜色来对这些扇形进行染色，相邻的两个扇形必须染上不同的颜色。问：一共有多少种不同的染色方法？

Example

input: m = 3, n = 3
output: 6

input: m = 5, n = 5
output: 1020

算法分析

首先考虑一个更简单的问题：对单列的方格进行染色。显然，这种情况下，染色方案数量为：

1
m * (m - 1)^(n - 1)

而圆盘问题，在此之上的变化只有一个，就是第1块和第n块的问题。第n块的染色不仅要考虑第n-1块，还有第1块。再进一步，其实决定性因素在于第n-1块。以下用color[i]表示第i块的颜色：

  1. 当color[1] == color[n-1]，此时第n块的可选颜色有m-1种。
  2. 当color[1] != color[n-1]，此时第n块的可选颜色有m-2种。

解决了第n块的颜色选择问题后，整个问题就很简单了，因为当m相同时，前n-2块的染色方案是不会因为块数的增加而改变的。因此，考虑使用动态规划的来解决问题。

假设m给定时，dp[i]表示圆盘分为i个扇形时的染色方案总数：

  1. 当color[1] == color[n-1]。这种情况下，我们可以将n-1,n,1这三个小扇形合并看作一个扇形，因为它们两端的颜色相同，所以不会对原来的情况造成改变。这样一共有n-2个扇形，且第n个扇形的可选颜色有m-1种，则有：

    1
    dp[i] = dp[i - 2] * (m - 1);

  2. 当color[1] != color[n-1]。这种情况下，假如忽略第n块，剩下的1至n-1块已经满足整个圆盘的染色需要，同时， 第n块的可选颜色有m-2种。那么：

    1
    dp[i] = dp[i - 1] * (m - 2);

综合上述两种情况，可以得到整个动态规划算法的状态转移方程：

1
dp[i] = dp[i - 2] * (m - 1) + dp[i - 1] * (m - 2);

初始状态如下：

1
2
3
dp[1] = m;
dp[2] = m * (m - 1);
dp[3] = m * (m - 1) * (m - 2);

代码实现

1
2
3
4
5
6
7
8
9
10
11
int Colour(int colour_number, int split_part) {
4int* dp = new int[split_part + 1]{ 0 };
4dp[1] = colour_number;
4dp[3] = colour_number * (colour_number - 1) * (colour_number - 2);
4for (int i = 4; i <= split_part; i++) {
44dp[i] = dp[i - 2] * (colour_number - 1) + dp[i - 1] * (colour_number - 2);
4}
4int answer = dp[split_part];
4delete dp;
4return answer;
}

以上实现针对单次计算。如果需要重复计算多次不同m,n值的方案，使用二维数组会更高效。

本文为博主原创文章，转载请注明出处。