LeetCode刷题实战：如何用动态规划解决哈密尔顿路径问题（附C++代码）
LeetCode实战：动态规划破解哈密尔顿路径问题的核心思路与代码实现
在算法竞赛和LeetCode刷题中，哈密尔顿路径问题因其NP完全的特性和巧妙的解法设计，常被视为检验动态规划功力的试金石。不同于教科书上的理论推导，本文将带您直击LeetCode真题，通过状态压缩和位运算技巧，将看似复杂的哈密尔顿路径问题转化为清晰的动态规划解决方案。
1. 哈密尔顿路径问题的动态规划本质
哈密尔顿路径要求遍历图中所有节点恰好一次，这与动态规划"状态转移"的思想天然契合。当我们面对LeetCode上的相关题目时，关键要抓住三个核心特征：
- 状态定义：用二进制位掩码表示节点访问状态（如
mask的第i位为1表示第i个节点已访问） - 状态转移：从当前已访问节点集合出发，尝试转移到未访问的相邻节点
- 终止条件：所有节点都被访问（即
mask所有位均为1）
以经典的Unique Paths III为例，二维网格中的无障碍方格就是待访问的节点，我们需要设计状态转移方程来记录访问路径。
// 状态表示：dp[mask][u] 表示已访问节点集合为mask，当前位于节点u时的路径数 vector<vector<int>> dp(1<<n, vector<int>(n, 0));2. 状态压缩与位运算技巧实战
高效处理节点访问状态是解题的关键。以下是状态压缩DP的典型操作模板：
int total = (1 << n) - 1; // 所有节点已访问的状态 for (int mask = 0; mask <= total; ++mask) { for (int u = 0; u < n; ++u) { if (!(mask & (1 << u))) continue; // 当前节点必须已访问 for (int v : graph[u]) { if (mask & (1 << v)) continue; // 不能重复访问 dp[mask | (1 << v)][v] += dp[mask][u]; } } }实际应用中还需要处理以下细节：
- 起始状态初始化：通常将起点对应的mask位置1
- 终止状态判断：检查mask是否覆盖所有必须访问的节点
- 空间优化：对于大规模问题可能需要滚动数组或哈希表优化
3. LeetCode 980. Unique Paths III 完整解析
让我们通过具体题目演示如何应用上述方法。该题要求在网格中从起点到终点，经过所有无障碍方格恰好一次。
3.1 问题建模与状态设计
首先将二维网格转化为图论模型：
- 每个无障碍方格视为图节点
- 相邻方格之间存在无向边
- 统计必须访问的节点数（包括起点和终点）
状态设计采用二维DP数组：
// dp[mask][pos] 表示在mask状态下位于pos位置的路径数 unordered_map<int, unordered_map<int, int>> dp;3.2 关键实现步骤
- 预处理阶段：
- 统计必须访问的方格数
target - 定位起点和终点坐标
- 统计必须访问的方格数
int start = 0, end = 0; int target = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] != -1) { int pos = i * n + j; target |= (1 << pos); if (grid[i][j] == 1) start = pos; if (grid[i][j] == 2) end = pos; } } }- 记忆化搜索实现：
int dfs(int mask, int pos) { if (pos == end) return mask == target ? 1 : 0; if (dp.count(mask) && dp[mask].count(pos)) return dp[mask][pos]; int res = 0; for (int dir : dirs) { int x = pos/n + dir[0], y = pos%n + dir[1]; if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == -1) continue; int next_pos = x * n + y; if (mask & (1 << next_pos)) continue; res += dfs(mask | (1 << next_pos), next_pos); } return dp[mask][pos] = res; }3.3 复杂度分析与优化
- 时间复杂度：O(n² * 2ⁿ)，其中n为必须访问的节点数
- 空间复杂度：O(n * 2ⁿ)
- 实际测试中，当n=20时仍可在合理时间内完成
4. 进阶应用：旅行商问题(TSP)的DP解法
哈密尔顿路径的DP思想可直接应用于经典的旅行商问题。以下是状态压缩DP解TSP的核心框架：
vector<vector<int>> dp(1<<n, vector<int>(n, INT_MAX)); dp[1][0] = 0; // 从城市0出发 for (int mask = 1; mask < (1<<n); ++mask) { for (int u = 0; u < n; ++u) { if (!(mask & (1<<u))) continue; for (int v = 0; v < n; ++v) { if (mask & (1<<v)) continue; dp[mask|(1<<v)][v] = min(dp[mask|(1<<v)][v], dp[mask][u] + dist[u][v]); } } } // 最终结果为所有城市访问完成后回到起点的最小成本 int res = INT_MAX; for (int u = 1; u < n; ++u) { res = min(res, dp[(1<<n)-1][u] + dist[u][0]); }实际编码时还需注意：
- 预处理距离矩阵：根据具体问题计算城市间距离
- 路径重建：通过记录前驱节点还原最优路径
- 对称性优化：固定起点减少重复计算
5. 高频面试考点与避坑指南
在技术面试中，面试官常通过哈密尔顿路径问题考察以下能力：
状态设计能力：
- 能否正确识别问题中的"节点"概念
- 能否合理设计表示访问状态的mask
边界条件处理：
- 起点和终点的特殊处理
- 必须访问节点与可选节点的区分
编码实现细节：
- 位运算的正确使用
- 记忆化搜索与递推的转换
常见错误包括：
- 忘记初始化起始状态
- 位运算优先级错误（建议多用括号明确）
- 状态转移时漏掉某些合法转移
- 未正确处理网格边界条件
调试技巧：打印中间状态时，可将mask转换为二进制字符串直观检查访问情况
6. 同类问题扩展与训练建议
掌握哈密尔顿路径的DP解法后，可尝试以下LeetCode题目巩固技能：
847. Shortest Path Visiting All Nodes
要求访问所有节点的最短路径，需结合BFS与状态压缩943. Find the Shortest Superstring
类似TSP的字符串拼接问题，需要预处理重叠部分996. Number of Squareful Arrays
排列问题中的哈密尔顿路径变种
训练建议：
- 先从网格类题目（如Unique Paths III）入手熟悉模型
- 尝试用不同方法（记忆化搜索、递推）实现相同问题
- 手动模拟小规模案例验证状态转移的正确性
- 比较位运算与bool数组两种状态表示的性能差异
在竞赛和面试准备中，建议建立自己的代码模板库，将状态压缩DP的通用部分封装成可复用的组件。例如：
class HamiltonianPathSolver { public: int solve(const vector<vector<int>>& graph, int start, int end) { n = graph.size(); target = (1 << n) - 1; // 初始化记忆化数组 memo.assign(1<<n, vector<int>(n, -1)); return dfs(1 << start, start, end, graph); } private: int n, target; vector<vector<int>> memo; int dfs(int mask, int u, int end, const vector<vector<int>>& graph) { if (mask == target) return u == end; if (memo[mask][u] != -1) return memo[mask][u]; int res = 0; for (int v : graph[u]) { if (!(mask & (1 << v))) { res += dfs(mask | (1 << v), v, end, graph); } } return memo[mask][u] = res; } };这种模块化的代码组织方式，既能提高解题速度，也便于在不同问题间迁移核心思想。