如何在手机上的九宫格密码上绘出最长距离？
转了一圈好像没人说子集 DP？暴力枚举应该没什么前途吧... 感觉这个问题用子集 DP，20 个点的计算应该没问题。 假设现在在一个 w 列 h 行的矩阵中，共有 n = wh 个点，然后要来画出一条最长的线。设函数 f(S, k) 表示使用仅使用集合 S 内的点，路线终止于 k 的所有方案中长度最长的方案的长度。子集 DP 转移的时候直接枚举 S 外的一个点 p ，检查目前从 k 到 p 连线是否合法，然后更新 f(S \cup \{p\}, p) 的值。初始时 f(\{i\},i)=0 。感觉学过的应该马上能想出来，如果不知道但又感兴趣的可以看下待会附带的代码。 时间复杂度 \Theta(2^nn^2) ，空间复杂度 \Theta(2^nn) 。速度当然会比直接枚举快很多。3 x 3 的矩阵的计算比 @酱紫君 的程序快了近 70 倍。 3 x 3 的矩阵： 具体方案： 4 x 4 的矩阵： 具体方案：（有点点混乱诶...） 时空复杂度都太大了，手里拿着的破机子跑不了 5 x 5 的。理论上空间复杂度可以优化为 O(2^n\sqrt{n}) ，<del>但如果不开多线程估计至少也要跑一个小时</del>。等什么时候有台好点的机子再跑吧。 感觉更大的情况可能只能找规律或者随机化乱搞了吧。不知道 5 x 5 的矩阵搜出来是什么样子的，感觉其中应该有规律可循。 UPD 2018.06.05 UPD 2018.06.06: 之前的程序有个小 BUG...现在已经改了...... 写了个空间复杂度优化了的版本，用了 4 个线程并行，结果好像比预期乐观太多了，只用了 1 分钟： 好像可以感觉到其中的规律了诶...貌似 3 x 3 和 5 x 5 就是经过正中心的一条旋转扫描线上来回滑动。虽然 5 x 5 最后几步有点鬼畜......虽然这个问题和 TSP 问题很像，但就目前来看我还是相信它不是 NP 难的，毕竟是一个特殊的图。 我多跑了几个其他的情况，不知道有没有大神能找出构造方法 新的程序有点长，就不整个贴在这了吧。程序可以在这里翻到。 附带主程序：