算法-递归和回溯

算法-递归和回溯

递归和回溯的基本概念：

• 递归的基本性质是函数调用，处理问题时，把大规模的问题不断的变小然后进行推导的过程。

• 回溯是利用递归的性质。从问题的起点出发。不断尝试，回头异步甚至多步做选择，知道最终抵达终点的过程。

递归(Recursion)

什么是递归，为什么叫递归？

递归有递有归

我认为递归需要几个要素：

1. 递归终止条件 什么时候停止递，开始归。

2. 递归递的条件 什么时候需要继续往下递。

3. 递归归的表达式（归的时候怎么做才能得到结果）

4. 提取重复的逻辑。缩小问题的规模。

   递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决。从程序实现的角度而言，我们需要抽象出一个干净利落的重复的逻辑，以便使用相同的方式解决子问题。

例题：

一条包含字母 A-Z 的消息通过以下方式进行了编码：

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: “12”
输出: 2
解释: 它可以解码为 “AB”（1 2）或者 “L”（12）。
示例 2:

输入: “226”
输出: 3
解释: 它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

解题思路

• 第一种情况是我们所有输入数字，每一个字符组合在一起算一个。
• 第二种情况是当前数字的前一个是1，或者前面是2且当前数字小于6，

解题步骤

1. 首先找到我们终止递开始归的条件，

   当前这个例子，我们需要查找到最后，没有问题才能记一个。

   也就是我们终止递开始归的条件是，当前元素已经是最后一个元素。

2. 什么时候需要继续往下递。

   当前例子，当我们还没有查找到最后一个元素的时候就需要继续递。

3. 递归归的表达式（归的时候怎么做才能得到结果）

   当前例子，我们有两种情况，也就是说当我们当前数字的前一个是1，或者前面是2且当前数字小于6的情况下，我们需要在记一个，然后在往前递，直到最后一个元素，算作一个，

const numDecodings = (s)=> {
    
    return decode(s,s.length-1);
};
const decode=(strs,i)=>{
    if(i<=0 ) return 1;// 递归终止条件
    let count=0;
    let curr=strs[i];
    let prev=strs[i-1];
    if(curr>'0'){// 没有到末尾继续递  这个为O(n)
        count=decode(strs,i-1);
    }
     if (prev == '1' || (prev == '2' && curr <= '6')) {
         count += decode(strs,i- 2);
         //这个为O(n-2)
         // 在归的途中途中，发现有满足条件的，需要做处理，
    }
    return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度

尝试时间复杂度方面的分析：

有两种分支：

1. 如果所有的数字都不满足prev == ‘1’ || (prev == ‘2’ && curr <= ‘6’)，她的时间复杂度为O(n)
2. 如果所有的数字都满足prev == ‘1’ || (prev == ‘2’ && curr <= ‘6’)，时间复杂度为O(n^n-2)

回溯（Backtracting）

回溯算法是一种试探算法。每一步都有多种尝试的可能性，是递归算法的变式，递归和回溯的区别我认为在于，在归的途中做的事情不一样，递归的每一次归都是确切的答案，而回溯的话，在归的时候。每一步都可能有多种尝试的可能。

例：

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]

解题思路

1. candidates的数可以重复使用。

解题步骤

1. 找到停止递开始归的条件

   当target减去元素的值小于-1的时候，说明这些元素的和大于了target，这样的组合不是正确的，开始归。

2. 归的时候做的事情

   每次归的时候都需要去查找还有没有别的组合 可以得到结果，所有的都需要去尝试，在递到末尾的时候，得到正确的组合之后，就推送到结果组里面了。target-元素-元素=0，说明组合元素是正确的。

3. 什么时候需要继续递

   在这个例子中，递的条件就是没有得到正确的组合以及值没有超出边界，就需要继续往下递。

   const combinationSum = (candidates, target)=> {
       let result=[];
       let solution=[];
       let length=candidates.length;
       const backTracking=(target,solution,start)=>{
           if(target<0) return;// 每次递下去，都需要对其的值进行判断
           if(target===0) { // 得到相等的，推送结果组合。开始归。
               result.push(solution);
               return;
           }
           for(let i=start;i<length;i++){
               solution.push(candidates[i]);// 将当前的值推送进数组
               backTracking(target-candidates[i],solution.slice(),i);// 递下去，target以及减去了一个元素的值，递下之后满足条件归，不满足条件继续递。
               solution.pop();
           }
       }
       backTracking(target,solution,0);
       return result;
   };
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19

时间复杂度

1. 这个例子，最外层循环一次，记O(n),如果我们每次都只需要递两次就可以得到答案的话。整个算法的时间复杂度为O(n^2)