LeetCode实战动态规划破解哈密尔顿路径问题的核心思路与代码实现在算法竞赛和LeetCode刷题中哈密尔顿路径问题因其NP完全的特性和巧妙的解法设计常被视为检验动态规划功力的试金石。不同于教科书上的理论推导本文将带您直击LeetCode真题通过状态压缩和位运算技巧将看似复杂的哈密尔顿路径问题转化为清晰的动态规划解决方案。1. 哈密尔顿路径问题的动态规划本质哈密尔顿路径要求遍历图中所有节点恰好一次这与动态规划状态转移的思想天然契合。当我们面对LeetCode上的相关题目时关键要抓住三个核心特征状态定义用二进制位掩码表示节点访问状态如mask的第i位为1表示第i个节点已访问状态转移从当前已访问节点集合出发尝试转移到未访问的相邻节点终止条件所有节点都被访问即mask所有位均为1以经典的Unique Paths III为例二维网格中的无障碍方格就是待访问的节点我们需要设计状态转移方程来记录访问路径。// 状态表示dp[mask][u] 表示已访问节点集合为mask当前位于节点u时的路径数 vectorvectorint dp(1n, vectorint(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_mapint, unordered_mapint, 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ⁿ)实际测试中当n20时仍可在合理时间内完成4. 进阶应用旅行商问题(TSP)的DP解法哈密尔顿路径的DP思想可直接应用于经典的旅行商问题。以下是状态压缩DP解TSP的核心框架vectorvectorint dp(1n, vectorint(n, INT_MAX)); dp[1][0] 0; // 从城市0出发 for (int mask 1; mask (1n); mask) { for (int u 0; u n; u) { if (!(mask (1u))) continue; for (int v 0; v n; v) { if (mask (1v)) continue; dp[mask|(1v)][v] min(dp[mask|(1v)][v], dp[mask][u] dist[u][v]); } } } // 最终结果为所有城市访问完成后回到起点的最小成本 int res INT_MAX; for (int u 1; u n; u) { res min(res, dp[(1n)-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 vectorvectorint graph, int start, int end) { n graph.size(); target (1 n) - 1; // 初始化记忆化数组 memo.assign(1n, vectorint(n, -1)); return dfs(1 start, start, end, graph); } private: int n, target; vectorvectorint memo; int dfs(int mask, int u, int end, const vectorvectorint 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; } };这种模块化的代码组织方式既能提高解题速度也便于在不同问题间迁移核心思想。
LeetCode刷题实战：如何用动态规划解决哈密尔顿路径问题（附C++代码）
LeetCode实战动态规划破解哈密尔顿路径问题的核心思路与代码实现在算法竞赛和LeetCode刷题中哈密尔顿路径问题因其NP完全的特性和巧妙的解法设计常被视为检验动态规划功力的试金石。不同于教科书上的理论推导本文将带您直击LeetCode真题通过状态压缩和位运算技巧将看似复杂的哈密尔顿路径问题转化为清晰的动态规划解决方案。1. 哈密尔顿路径问题的动态规划本质哈密尔顿路径要求遍历图中所有节点恰好一次这与动态规划状态转移的思想天然契合。当我们面对LeetCode上的相关题目时关键要抓住三个核心特征状态定义用二进制位掩码表示节点访问状态如mask的第i位为1表示第i个节点已访问状态转移从当前已访问节点集合出发尝试转移到未访问的相邻节点终止条件所有节点都被访问即mask所有位均为1以经典的Unique Paths III为例二维网格中的无障碍方格就是待访问的节点我们需要设计状态转移方程来记录访问路径。// 状态表示dp[mask][u] 表示已访问节点集合为mask当前位于节点u时的路径数 vectorvectorint dp(1n, vectorint(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_mapint, unordered_mapint, 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ⁿ)实际测试中当n20时仍可在合理时间内完成4. 进阶应用旅行商问题(TSP)的DP解法哈密尔顿路径的DP思想可直接应用于经典的旅行商问题。以下是状态压缩DP解TSP的核心框架vectorvectorint dp(1n, vectorint(n, INT_MAX)); dp[1][0] 0; // 从城市0出发 for (int mask 1; mask (1n); mask) { for (int u 0; u n; u) { if (!(mask (1u))) continue; for (int v 0; v n; v) { if (mask (1v)) continue; dp[mask|(1v)][v] min(dp[mask|(1v)][v], dp[mask][u] dist[u][v]); } } } // 最终结果为所有城市访问完成后回到起点的最小成本 int res INT_MAX; for (int u 1; u n; u) { res min(res, dp[(1n)-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 vectorvectorint graph, int start, int end) { n graph.size(); target (1 n) - 1; // 初始化记忆化数组 memo.assign(1n, vectorint(n, -1)); return dfs(1 start, start, end, graph); } private: int n, target; vectorvectorint memo; int dfs(int mask, int u, int end, const vectorvectorint 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; } };这种模块化的代码组织方式既能提高解题速度也便于在不同问题间迁移核心思想。
