0. 概念

  • DFS：深度优先搜索算法
    • 解法1：递归
    • 解法2：非递归，使用stack
  • 递归是一种算法结构，回溯是一种算法思想。
    • 回溯：通过不同的尝试，来生成问题的解。有点类似穷举，和穷举不同的是回溯会“剪枝”
    • 回溯是DFS的一种。回溯在求解过程中不保留完整的数结构，而DFS记下完整的搜索树。
  • 动态规划和回溯算法的异同：
    • 动态规划的暴力求解阶段就是回溯算法。
    • 动态规划有重叠子问题性质，可以使用dp table或者备忘录优化，进行剪枝。
    • 回溯算法没有重叠子问题性质。

DFS 回溯 - 图1

1. DFS模板

  1. // dfs模板， 记忆化减枝
  2. void dfs(路径，选择列表) {
  3.     if (终止条件) {
  4.         存放结果; // 若只需要一个解，只需要检查dfs的返回值，直接返回即可
  5.         return;
  6.     }
  8. for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { // 如上下左右等，(有时，需按照题意，构造选择的集合)
  9.         // 排除不合法的选择;或者已经做过的选择
  10.         // 做选择;同时将该选择从选择列表中移除
  11.         dfs(路径，选择列表); // 递归
  12.         // 回溯，撤销选择，将该选择再加入选择列表
  13.     }
  14. }

2. Examples

  1. // eg. 93. 复原 IP 地址
  2. class Solution {
  3. public:
  4.     vector<string> ans;
  5.     string tmpString;
  6.     vector<string> restoreIpAddresses(string s) {
  7.         dfs(s, 0, 0);
  8.         return ans;
  9.     }
  11.     void dfs(string &s, int index, int count)
  12.     {
  13.         if (count == 4 || s.size() == index) {
  14.             if (count == 4 && s.size() == index) {
  15.                 ans.push_back(tmpString.substr(0, tmpString.size() - 1));
  16.             }
  17.             return;
  18.         }
  20.         for (int i = 1; i <= 3; i++) {
  21.             // 排除不合法的选择选择
  22.             if (index + i > s.size()) {
  23.                 continue;
  24.             }
  25.             if (s[index] == '0' && i != 1) {
  26.                 continue;
  27.             }
  28.             if (i == 3 && s.substr(index, i) > "255") {
  29.                 continue;
  30.             }
  31.             tmpString += s.substr(index, i);
  32.             tmpString += ".";
  33.             dfs(s, index + i, count + 1);
  34.             // 撤销选择
  35.             tmpString = tmpString.substr(0, tmpString.size() - i - 1);
  36.         }
  37.     }
  38. };