|
最近在准备蓝桥杯的比赛，于是做了历年的真题，碰到”回路计算“问题后，思考许久之后，才明白答案代码的含义。
问题如下：
蓝桥学院由21栋教学楼组成，教学楼编号1到21。对于两栋教学楼a和b,当a和b互质时，a和b之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。
小蓝现在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路），请问他有多少种不同的访问方案？两个访问方案不同是指存在某个i,小蓝在两个访问方法中访问完教学楼i后访问了不同的教学楼。
?
答案代码如下：
from math import gcd
n = int(input())
m = 1 << n
dp = [[0 for j in range(n)] for i in range(m)]
load = [[False for j in range(n)] for i in range(n)]
for i in range(1, n + 1):
for j in range(1, n + 1):
if gcd(i, j) == 1:
load[i - 1][j - 1] = True
dp[1][0] = 1
for i in range(1, m):
for j in range(n):
if i >> j & 1:
for k in range(n):
if i - (1 << j) >> k & 1 and load[k][j]:
dp[i][j] += dp[i - (1 << j)][k]
print(sum(dp[m - 1]) - dp[m - 1][0])
现对该问题以及代码进行详细说明。
该问题的解法为”状态压缩DP“，在该问题中，一共有2的21次方种状态（从全为0到全为21个1），用二进制表示，例如00000000000000000001，每一位代表一栋教学楼，该位置上为1代表该教学楼已经遍历过，0代表该教学楼没有遍历过。
最终的目标为1111·····111（21个1），由于我们从第一栋教学楼出发的，因此初始首位就有一个1（初始状态，即第2种状态，000······0001）
可以知道，每一种状态对应一种遍历的中途过程。
dp[i][j]存储了第i+1个状态，并且该状态以第j+1栋教学楼为终止节点的方案数。对于某一种状态，由于遍历顺序的不同，因此终止节点可能不同。
dp[1][0]=1,该等式左边表示第2种状态（000······1），且该状态以第一栋教学楼为终止节点的方案数，并赋值为1.我们就是从第一栋教学楼出发的，这可以理解。
状态之间具有转化关系（这里是节点数相差为1的状态间的转化）。例如：000···111（dp[7]）可能从000······110(dp[6])、000······101(dp[5])、000······011(dp[3])转化而来。可以看出是其中一个0变成了1.而转化过程与连通与否相关。因此要考虑转化前后状态的具体终止结点，二者互质才可连通。
于是，从dp[1]开始递推，最终得到dp[m-1](m为2的21次方)，随谓dp[m-1],是一个列表，列表中的元素（数字）代表方案数，以不同教学楼为终止节点的方案数，111······111，该列表有21个元素。得到111······111该状态后，并不是最终结果，因为该状态只是表明所有教学楼都只走过一遍，但没有回到第一栋教学楼，由于1和任何数互质，因此无论以哪一栋教学楼为终止节点（只要不是第一栋教学楼），就能回到起点。
sum(dp[m - 1]) - dp[m - 1][0]即为最终答案。
|