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

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

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

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

打勾的表示拿,打叉的表示不拿,如果拿了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);
        }

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

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

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

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

  private void dfs(char[] str, int index, HashSet<String> 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);
    }
  }

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

03-30 15:26