我一直在困扰这个问题很长一段时间。它必须有一个动态编程解决方案，因为它已被标记为“动态编程”。请提出一种方法。动态规划：Timus Online Judge 1172船舶路线
删节问题陈述：
有3个岛屿为他们每个人的n个城市。从一个岛上的每个城市到另一个岛上的每个城市都有一条路径，即。没有连接同一岛屿上的城市的道路。找出访问所有3 * N城市的方式。请注意，如果3 * N个城市的继承是相同的，或者如果第一次旅行的3 * N个城市的继承与第二次旅行的3 * N个城市的继承相同，那么2次旅行是相同的，向后读（例如，如果每个岛屿都有1个城市，按照岛的编号进行编号，则1-2-3-1和1-3-2-1的行程将相同）。
限制条件：
1≤N≤30
样品输入/输出：
对于N = 2，答案= 16
这只是我的想法：
首先，我们可以解决这个问题，如果我们能够解决两个子问题
假设您需要生成长度为3 * N只有1发一个字符串，2或3，怎么算我们可以通过很多方式创建这个字符串，条件是没有连续的两次出现,1,2或3，并且对于每种类型的字符，字符串中应该有N个字符。你可以解决这个使用DP
其次，从所有的字符串创建，删除第一个字符，因为条件的该字符串可以读取同样向后和向前，所以每个字符串除了回文被计算两次，。所以，我们需要计算那些3 * N - 1字符串的回文数。这可以通过DP
来解决而且，现在，我们可以用一个城市取代1,2或3每个位置的字符串中岛1，2或3，有（N！）^ 3方式来做每个字符串，我们有答案
大部分是正确的，但我认为（包括重复）有（N-1）！N！N！如何将不同的城市分配到岛屿参观，因为每个岛屿的城市都可以独立分配。 –
另一个想法是：没有回文，因为每个城市只有一次访问:)我们只需要一个约束，例如“只计算第一个城市所访问的路径比最后一个城市访问次数更少”，但它很复杂，因为第一个和最后一个城市可能在同一个岛上或不同的岛屿上。 –
@j_random_hacker实际上字符串的长度应该是3 * N + 1，第一个和最后一个字符是一样的，所以我认为它需要被修正：D –
你到目前为止提出了什么方法/解决方案？并且人们可能能够从那里指导你。 – lzcd
我相信你的意思是“找到访问所有3N城市的方式的数量”，而不是“N”？当然，从其中一个开始并且必须在最后返回的限制也必须成立。 – lightalchemist
@lightalchemist是的，我的意思是在一个循环中访问3个城市。我编辑了这个问题。 –