关于递归和回溯的一次深入思考

业余算法coder，平时做得最多的数据结构算法就是模拟，很久之前学过递归，后来接触到回溯之后，一直很懵，同样的递归，回溯除了要进行“复原”以外，为什么会多一个for循环。之前一直没搞懂这个问题，也没有去深究。直到昨天lc的每日一题，我一眼看出来可以用递归解，用递归写了半天都不会，然后看大佬写的回溯，又是for循环中去递归，就好像是以前的质变引起量变了一样，我突然就悟了。

贴一道经典递归题：打家劫舍

“有一个数组values=[5,9,6,2,4,1,3,7,10]，小偷不能偷相邻的财报，也就是说，小偷偷了第一个5之后，就不能偷第二个9了”

这种就是标准的递归二叉树结构：

打勾的表示拿，打叉的表示不拿，如果拿了5，就只有考虑6拿不拿了，如果不拿5，就可以考虑9拿不拿，就这样一直决策下去，取价值最大的一种方法。

代码如下：

        public int dfs(int[] nums, int idx, int curValue) {
            if (idx >= nums.length) {
                return curValue;
            }
	    // 当前这个拿，去下一个决策
	    int no = dfs(nums, idx + 1, curValue);
			
	    // 当前这个拿，下一个就肯定不能拿了，得去下一个的下一个做决策
            int yes = dfs(nums, idx + 2, curValue + nums[idx]);

            return Math.max(no, yes);
        }

再来贴一道经典回溯题：打印子序列

假如有一个字符串 abcd，那么它的子序列为 : a,b,c,d,ab,ac,ad,bc,bd,cd

这种就是标准的回溯结构：

也就是在这里，我搞明白了为什么需要一个for'循环，上面的模型，只有一棵树，而回溯，每个点都能成为一棵树，所以每个for循环的时候，就是以这个点开始遍历树。

  private void dfs(char[] str, int index, HashSet ans, String path) {
    if (index >= str.length) {
      ans.add(path);
      return;
    }
    // 分别以 a,b,c,d 为头节点遍历整棵树
    for (int j = index; j < str.length; j++) {
      // 当前值拿的情况，去遍历
      path += str[j];
      dfs(str, j + 1, ans, path);
      // 回溯精髓：复原
      path = path.substring(0, path.length() - 1);
      // 当前值不拿的情况，去遍历
      dfs(str, j + 1, ans, path);
    }
  }

后面会更新一下从递归到记忆化搜索和动态规划的方法，动态规划并不是一蹴而就，转移方程也不是直接看出来的，原始的方法就是从递归优化到动态规划。