recursion - 面试问题（较大输入的着色网格hackerrank问题）

Question

我最近在为某家公司做hackerrank测试，遇到了以下问题。我搜索并发现它对于给定的约束是不可解决的（NP-hard）。如果您知道如何解决这个问题，请告诉我。

问题

计算使用 K 种颜色为 N * M 网格着色的方法数。网格中相邻的方块应该有不同的颜色。如果正方形共享一条边，则认为它们是相邻的。

约束 : 1<=N,W,K<=10^5 使用 10^9 +7 取模后要求打印上面得到的答案

谢谢

标签： recursiondynamic-programming

Answer 1

根据我在这里找到的解决方案是 jernej 在堆栈交换中发布的问题的详细解释。下面贴出链接。

Read 和 Tutte 的问题。您本质上是在询问网格图的色多项式（1 次顶点无关紧要。）请参阅 Read RC 和 WT Tutte 的附图。色多项式。在：LW Beineke 和 RJ Wilson，图论选题，第 3 卷，第 15--42 页。