状压 DP 问题描述 状态压缩动态规划是指用二进制数表示状态的动态规划。 常见的有旅行商问题、集合划分等。 通常用一个整数的二进制位表示元素的选择状态。 旅行商问题(TSP) 算法思想 定义dp[state][i]表示已访问城市集合为state且当前在城市i的最小代价 枚举下一个要访问的城市j 状态转移方程：dp[state | (1<<j)][j] = min(dp[state][i] + cost[i][j]) 最终答案为dp[(1<<n)-1][end] 代码实现 c++ java python int tsp(vector<vector...