2023-07-09：给定N、M两个参数，一共有N个格子，每个格子可以涂上一种颜色，颜色在M种里选，当涂满N个格子，并且M种

2023-07-09：给定N、M两个参数，

一共有N个格子，每个格子可以涂上一种颜色，颜色在M种里选，

当涂满N个格子，并且M种颜色都使用了，叫一种有效方法。

求一共有多少种有效方法。

1

答案2023-07-09：

这两种算法用于计算涂色的有效方法总数。

算法 ：

1.初始化路径数组 ，颜色是否使用的数组 。

2.调用  函数，传入初始参数：路径数组 ，颜色是否使用的数组 ，当前处理的位置 ，格子数量 ，颜色种类 。

3.如果当前位置  等于格子数量 ，即路径数组  已填满：

• 将颜色是否使用的数组  中所有元素重置为 。

• 统计路径数组  中不重复的颜色数量，并记录在  中。

• 如果  等于颜色种类 ，说明此路径是有效方法，返回 1；否则返回 0。

4.否则，遍历颜色种类  的所有可能颜色：

• 在路径数组  当前位置  处填入该颜色。

• 调用  函数递归处理下一个位置 。

• 将返回的结果累加到  上。

5.返回最终的结果 。

算法 ：

1.初始化动态规划数组 ，大小为 。

2.对于  数组的第一行，设置每个位置的值为颜色种类 。

3.使用两层循环，从第二行开始，依次计算每个位置  的值：

•  等于前一行  乘以颜色种类  取模 。

• 添加额外的项， 等于前一行  乘以剩余颜色种类 ，然后加上之前的结果，再取模 。

4.返回  的结果作为最终的答案。

功能测试：逐个测试从 1 到 9 的格子数量和颜色种类的组合，比较两种算法的结果是否一致，如果不一致则输出错误信息并中断。

性能测试：以 N=5000、M=4877 为例，计算两种算法的运行时间并打印结果。

算法  的时间复杂度为O(m^n)，空间复杂度为O(n)。

算法  的时间复杂度为O(nm)，空间复杂度为O(nm)。

go完整代码如下：

在这里插入图片描述rust完整代码如下：

在这里插入图片描述c++完整代码如下：

在这里插入图片描述