回溯算法

什么是回溯算法

回溯算法是一种基于试错思想的算法，通常用于在候选解的所有可能的情况中搜索并找出满足条件的解。

回溯算法的基本思路是，从问题的某一种状态开始搜索，搜索过程中不断尝试每一种可能的选择，直到找到满足条件的解或者所有可能的选择都已尝试完毕。如果当前的选择不能导致满足条件的解，就回溯到上一个状态并尝试其他选择。

回溯算法通常使用递归来实现。在递归函数中，每一层表示问题的一个状态，递归过程中不断地进行选择和回溯操作。

在应用回溯算法时，需要注意以下几点：

定义问题的状态：回溯算法的关键在于定义问题的状态以及如何进行选择和回溯。

定义递归函数：通常使用递归函数实现回溯算法，需要注意递归的边界条件和返回值。

剪枝优化：回溯算法的搜索空间往往非常大，需要使用剪枝技巧来减少不必要的搜索，提高算法的效率。

回溯算法可以应用于很多问题，例如求解数独、八皇后问题、组合问题、子集问题等。

简单理解的话：就是方法体内多次调用该方法，其实就是回溯了。

什么问题适合回溯算法

某算法需要n个步骤，而执行每个步骤时又有多种选择可以执行，符合这种问题的都可以使用回溯算法来解决。

而动态规划也是分为多个步骤，每个步骤有多重选择，所以动态规划问题都可以使用回溯算法来解决，而动态规划一般是用于最优解，所以如果用回溯算法来解决动态规划问题的话，回溯递归终止条件通常是取最优解(最大，最小值)

回溯算法特别注意的点

1.回溯算法对于可变类型一定要恢复要回溯之前的状态，不可变类型不需要恢复到回溯之前的状态，具体可以查看这篇文章,下面的前4个例子都可以体现这点。

2.回溯通常会有很多重复子问题，我们需要使用备忘录(缓存的方式)来进行剪纸操作，需要特别注意的点是缓存通常是使用HashMap来实现的，而HashMap也是可变类型，所以一定要记得将HashMap恢复到回溯之前的状态，可看下面的第5个和第6个例子和第7个例子。

3.回溯有很多重复子问题，动态规划其实也有很多重复子问题，也需要使用备忘录模式来剪枝。

备忘录模式需要注意的点

回溯通常会有很多重复子问题，我们需要使用备忘录(缓存的方式)来进行剪纸操作。

通常可使用以下3种类型来进行缓存

• ArrayList
  可存储相同元素的值
  • 新增元素:使用add()方法

  List<Integer> list = new ArrayList<>();
  list.add(100);
  

  • 删除元素: 可通过下标进行删除，通常如下

  list.remove(list.size()-1);
  

  • 判断元素是否存在 :需要注意的是下面是判断100这个元素是否在该数组中，而不是100下标的元素是否在数组中

  if(list.contains(100)){
            
  }
  

• HashSet
  只能存储key为不重复的值，如果存在，后者覆盖前者
  • 新增元素

   HashSet<Integer> list = new HashSet<>();
   list.add(200);
  

  • 删除元素:需要特别注意,remove删除的是元素，而不是和ArrayList那样删除的下标，不能这样删除list.remove(list.size()-1)

   list.remove(200);
  

  • 判断元素是否存在,注意判断的也是元素而不是下标

  if(list.contains(200)){
         
  }
  

• HashMap
  只能存储key为不重复的值，如果存在，后者覆盖前者。使用该方式的话，通常key为元素值，value为Booble类型，true表示该key已经存在。
  • 新增元素:如下表示100这个元素被访问过

  HashMap<Integer,Boolean> list = new HashMap<>();
  list.put(100,true);
  

  • 删除元素：可以使用以下俩种方式

  //删除该元素，注意是元素key，而不是下标
  list.remove(100);
  //将该元素赋值为false
  list.put(100,false);
  

  • 判断元素是否存在:可以看到使用containsKey&& get，因为value值的类型为Booble类型，该类型的默认值是NULL,如果100这个key不存在时使用list.get(100)将会报空指针问题，所以前边必须containsKey(100)进行判断下

  if(list.containsKey(100) && list.get(100)){
            
   }
  

备忘录key的类型容易踩的坑

• HashSet的key能用StringBuffer类型存储吗？

先抛出问题，可以看下面的单词拆分的例子，使用的是cache.add(x.toString()) 而不是cache.add(x);

x变量是StringBuffer类型，发现直接cache.add(x)之后代码并不生效，必须将StringBuffer转换为String类型之后才会生效，这是为什么呢？

结论是可变类型的 StringBuffer 转化为不可变类型的字符串类型 String 才能加入到 HashSet 中进行判断，因为 HashSet 中判断元素是否相同是通过 hashCode() 和 equals() 进行判断的，而 StringBuffer 类型并没有重写 hashCode() 和 equals() 方法，所以加入到 HashSet 中后，判断时会出现错误。

也就是说如果HashSet、HashMap使用StringBuffer类型作为key时contains()判断是不生效的,必须转化成String类型才可以。

• HashMap的key能用数组存储吗？

HashMap的key用数组存储时，判断key是否存在是会错误的，具体可以看49的字母异位词分组算法题。

发现必须得将数组转换为String类型才能作为HashMap的key，判断key是否存在才会成功，这是什么原因呢？

在 Java 中，数组是通过其内部的物理地址进行比较的，而不是通过它们的内容进行比较。因此，当使用 char[] 作为哈希映射的键时，由于其比较操作是基于其地址的，而不是基于其内容的，所以会导致哈希表无法正常工作。

在这种情况下，应该使用 String 类型作为哈希映射的键，而不是 char[] 数组。您可以将 char[] 数组转换为 String 类型，然后将其用作哈希映射的键，例如

String key = new String(strArr);
List<String> item = cache.getOrDefault(key, new ArrayList<>());

• 总结

HashSet、HashMap的key的类型是基础类型，不要使用数组、StringBuffer等可变类型，这些类型在判断key是否存在时都会出现问题

回溯算法举例

• 编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：
1.插入一个字符
2.删除一个字符
3.替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

/**
 * 本方法使用回溯算法，递归所有可能
 */
class Solution {
    int min = Integer.MAX_VALUE;
    char[] char1;
    char[] char2;
    //用于存储word1数组下标为i时且word2数组下标为j时，修改的次数，key=i*10+j
    HashMap<Integer,Integer> route;
    public int minDistance(String word1, String word2) {
        char1 = word1.toCharArray();
        char2 = word2.toCharArray();
        int char1Length = char1.length,char2Length = char2.length;
        route = new HashMap<>();
        operation(0,0,char1Length,char2Length,0);
        return min;
    }

    /**
     * 当word1数组下标为i时且word2数组下标为j时，返回修改的editCnt次数
     * @param i word1数组的下标
     * @param j word2数组的下标
     * @param char1Length word1数组的
     * @param char2Length word2数组的
     * @param editCnt 修改的次数
     */
    public void operation(int i,int j,int char1Length,int char2Length,int editCnt){
        //i*10+j可以作为唯一key,若key存在则说明已经遍历过该位置了，如果当前的editCnt比Value大则直接返回即可
        if(route.containsKey(i*10+j) && route.get(i*10+j) < editCnt){
            return;
        }
        route.put(i*10+j,editCnt);
        //word1数组已经遍历完，则计算word2剩余的长度，该长度是word1添加数据的长度
        if(i == char1Length ){
            editCnt += char2Length-j;
            min = Math.min(editCnt,min);
            return;
        }
        //word2数组已经遍历完，则计算word1剩余的长度，该长度是word1删除数据的长度
        if(j == char2Length ){
            editCnt += char1Length-i;
            min = Math.min(editCnt,min);
            return;
        }
        //如果俩值相同则下标都下移，且操作次数不增加
        if(char1[i] == char2[j]){
            operation(i+1,j+1,char1Length,char2Length,editCnt);
        }else{
            //编辑距离一共有3种操作
            //word1 i下标前新增一个和word2 小标j相同的元素
            operation(i,j+1,char1Length,char2Length,editCnt+1);
            //删除world1下标为i的元素
            operation(i+1,j,char1Length, char2Length,editCnt+1);
            //修改world1下标为i的元素与之word2下标j元素相同
            operation(i+1,j+1,char1Length, char2Length,editCnt+1);
        }
    }
}

• 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

此算法可以看到递归函数上List<Integer> target，List属于可变类型，所以
Collections.swap(target,i,index)之后要恢复到回溯之前的状态Collections.swap(target,i,index);

class Solution {
 public List<List<Integer>> permute(int[] nums) {
       List<List<Integer>> result = new ArrayList<>();
       List<Integer> target = new ArrayList<>();
       for (int i=0;i<nums.length;i++){
           target.add(nums[i]);
       }
        route(result,0,target,target.size());
       return result;
    }
    public void route(List<List<Integer>> result,int index,List<Integer> target,int length){
        if(index == length-1){
            result.add(new ArrayList<>(target));
            return;
        }
        for (int i=index;i<length;i++){
            Collections.swap(target,i,index);
            route(result,index+1,target,length);
            Collections.swap(target,i,index);
        }
    }
}

• 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

可以看出递归函数有一个StringBuffer str变量，该变量属于可变类型，所以需要在append()之后在此deleteCharAt()。
而递归函数上的int index,int length,String digits都是属于不可变变量，所以在+1之后并不需要-1。

class Solution {
    Map<Character,Character[]> result;
    public List<String> letterCombinations(String digits) {
        List<String> ret = new ArrayList<>();
        if(digits.length() == 0){
            return ret;
        }
        result = new HashMap<>();
        result.put('2',new Character[]{'a','b','c'});
        result.put('3',new Character[]{'d','e','f'});
        result.put('4',new Character[]{'g','h','i'});
        result.put('5',new Character[]{'j','k','l'});
        result.put('6',new Character[]{'m','n','o'});
        result.put('7',new Character[]{'p','q','r','s'});
        result.put('8',new Character[]{'t','u','v'});
        result.put('9',new Character[]{'w','x','y','z'});
        int a = digits.length();
        findResult(ret,0,digits.length(),new StringBuffer(),digits);
        return ret;
    }

    public void findResult(List<String> ret,int index,int length,StringBuffer str,String digits){
        //除了通过 String 类创建和处理字符串之外，还可以使用 StringBuffer 类来处理字符串。StringBuffer 类可以比 String 类更高效地处理字符串。
        //因为 StringBuffer 类是可变字符串类，创建 StringBuffer 类的对象后可以随意修改字符串的内容。每个StringBuffer 
        //类的对象都能够存储指定容量的字符串，如果字符串的长度超过了 StringBuffer 类对象的容量，则该对象的容量会自动扩大。

        //注意这里的判断条件是index == length而不是index == length-1，index为length-1时还需要继续遍历呢
        if(index == length){
            //注意：这里要重新new一个String对象，还有另一种写法ret.add(str.toString())
            ret.add(new String(str));
            return;
        }
        Character[] value = result.get(digits.charAt(index));
        for (int i=0;i<value.length;i++){
            //str末尾追加一个字符
            str.append(value[i]);
            findResult(ret,index+1,length,str,digits);
            //把str最末尾的字符在删除
            str.deleteCharAt(str.length()-1);
        }
    }
}

• 有效括号的生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

这个算法也是递归函数上看到了有可变类型StringBuffer str，在append()之后需要deleteCharAt()

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        search(result,new StringBuffer(),0,0,n);
        return result;
    }
    public void search(List<String> result,StringBuffer str,int leftNum,int rightNum,int n){
        if(str.length() == n*2){
            result.add(new String(str));
            return;
        }
        if(leftNum<n){
            search(result,str.append("("),leftNum+1,rightNum,n);
            str.deleteCharAt(str.length()-1);
        }
        if(leftNum>rightNum && rightNum<n){
            search(result,str.append(")"),leftNum,rightNum+1,n);
            str.deleteCharAt(str.length()-1);
        }
    }

}

• 最短路径
  给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

可以看出使用HashMap来进行剪枝操作。每次操作之前都会ret.put()，由于HashMap是可变类型，所以在回溯之后一定要恢复到回溯之前的状态，也就是必须ret.remove()

class Solution {
    int min= Integer.MAX_VALUE;
    Map<Integer,Integer> ret;
    public int minPathSum(int[][] grid) {
        ret = new HashMap<>();
        minSum(0,0,grid[0][0],grid);
        return min;
    }

    /**
     * 获得grid[i][j]的总和
     * @param i 一维下标
     * @param j 二维下标
     * @param sum 表示grid[i][j]的总和，注意不是grid[i][j]的最小和
     * @param grid
     */
    public void minSum(int i,int j,int sum,int[][] grid){
        //进行剪枝，如果当前ret.get(i*10+j)<sum，则本次可以退出循环
        if(ret.containsKey(i*10+j) && ret.get(i*10+j)<sum){
            return;
        }
        ret.put(i*10+j,sum);
        if(i == grid.length-1 && j==grid[0].length-1){
            //获取到达grid[grid.length-1][grid[0].length-1]时的最小值
            min = Math.min(sum,min);
            return;
        }
        //当i到最底部的时候，只能向右边走
        if(i == grid.length-1){
            minSum(i,j+1,sum+grid[i][j+1],grid);
        }else if(j== grid[0].length-1){
            //当j到达最右边的时候，只能向下走
            minSum(i+1,j,sum+grid[i+1][j],grid);
        }else{
            //平时可以向下、向右走
            minSum(i+1,j,sum+grid[i+1][j],grid);
            minSum(i,j+1,sum+grid[i][j+1],grid);
        }
        ret.remove(i*10+j);
    }
}

• 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

本算法可以看出nums和exist都是可变类型，所以要在恢复到回溯之前都要remove()

/**
 * 本结题使用回溯+备忘录方式
 */
class Solution {
    List<List<Integer>> ret;
    //子数组中会有很多位置不同的相同元素，比如[1,2,2]和[2,1,2]这种，该题需要排除这类情况，
    //可以将数组排序然后拼接所有元素作为hash key
    HashSet<String> exist;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        ret =new ArrayList<>();
        exist = new HashSet<>();
        ArrayList<Integer> allowNum = new ArrayList<>();
        //candidates数组中比target值大的元素直接排除就好
        for (int i=0;i<candidates.length;i++){
            if(candidates[i]<=target){
                allowNum.add(candidates[i]);
            }
        }
        backtrack(allowNum,new ArrayList<Integer>(),0,target);
        return ret;
    }

    /**
     * @param allowNum 遍历的数组
     * @param nums 返回的子数组
     * @param sum nums数组的所有元素和
     * @param target nums数组所有元素和的目标值
     */
    public void backtrack(ArrayList<Integer> allowNum,ArrayList<Integer> nums,int sum,int target){
        String hashCode="";
        if(sum == target){
            ArrayList<Integer> newList = new ArrayList<>(nums);
            hashCode = hashArray(newList);
            if(!exist.contains(hashCode)){
                //注意re他的类型是HashMap属于可变类型，所以需要在恢复到回溯之前ret.remove()
                ret.add(newList);
                exist.add(hashCode);
            }
            return;
        }
        if(sum>target){
            return;
        }
        //可以看到每次都是从下标0开始循环，因为该题可存在重复元素，比如allowNum为[2,4],nums为[2,2]也是满足条件的
        for (int i=0;i<allowNum.size();i++){
            //由于nums为ArrayList类型，属于可变类型，所以在恢复到回溯之前一定要remove
            nums.add(allowNum.get(i));
            backtrack(allowNum,nums,sum+allowNum.get(i),target);
            nums.remove(nums.size()-1);
        }
        //记得这里要remove哦
        exist.remove(hashCode);
    }

    /**
     * 将目标数组target进行排序后拼接所有元素，返回hash key
     * @param target
     * @return
     */
    public String hashArray(List<Integer> target){
        String number = "";
        Collections.sort(target);
        for (int i=0;i<target.size();i++){
            number+=String.valueOf(target.get(i));
        }
        return number;
    }
}

• 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

使用回溯算法，并且使用缓存用来剪枝，由于HashMap属于可变类型，所以一定要恢复到回溯之前的状态cache.put(mIndex*n+nIndex,false);

class Solution {
    int routeCnt = 0;
    HashMap<Integer, Boolean> cache;

    public int uniquePaths(int m, int n) {
        cache = new HashMap<>();
        route(m,0,n,0);
        return routeCnt;
    }

    public void route(int m, int mIndex, int n, int nIndex) {
        if (mIndex == m - 1 && nIndex == n - 1) {
            routeCnt++;
            return;
        }
        if(cache.containsKey(mIndex*n+nIndex) && cache.get(mIndex*n+nIndex)){
            return;
        }
        cache.put(mIndex*n+nIndex,true);
        if(mIndex == m-1){
            //只能往右
            route(m,mIndex,n,nIndex+1);
        }else if(nIndex == n-1){
            //只能向下
            route(m,mIndex+1,n,nIndex);
        }else{
            //可向下也可向右
            route(m,mIndex,n,nIndex+1);
            route(m,mIndex+1,n,nIndex);
        }
        cache.put(mIndex*n+nIndex,false);
    }
}

• 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3：

/**
 * 此题使用回溯法，大致分为俩步
 * 1.找到word第一个字符在board中的下标，然后从该下标开始寻找，如果找到一条路径满足word，则直接返回true接口
 * 2.可以发现，下一步可以走上下左右4个方向，也就是说有4种可能，且题目中要求同一个单元格内的字母不允许被重复使用，
 * 所以需要HashSet来记录走过的路径；也就是说走上下左右4个方向且不能被访问
 */
class Solution {
    boolean flag;

    public boolean exist(char[][] board, String word) {
        char[] charWord = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == charWord[0]) {
                    //第一步找到word第一个字符在board中的下标，然后从该下标开始遍历
                    backTrack(board, i, j, new HashSet<>(), 0, charWord);
                    //只要有一个返回true则return
                    if (flag) {
                        return true;
                    }
                }
            }
        }
        return flag;
    }

    /**
     * 判断board[i][j]元素是否与charWord[index]元素是否相同
     */
    public void backTrack(char[][] board, int i, int j, HashSet<Integer> cache, int index, char[] charWord) {

        if (index >= charWord.length) {
            //表示charWord的所有元素都遍历完了，返回true
            flag = true;
            return;
        }
        if (i > board.length - 1 || i < 0 || j > board[0].length - 1 || j < 0) {
            return;
        }
        //如果board[i][j]已经被访问过或者不等于charWord[index]则表示该路径不可用，直接return
        if (cache.contains(i * board[0].length + j) || board[i][j] != charWord[index]) {
            return;
        }
        //记录节点状态,表示被访问
        cache.add(i * board[0].length + j);
        backTrack(board, i + 1, j, cache, index + 1, charWord);
        backTrack(board, i - 1, j, cache, index + 1, charWord);
        backTrack(board, i, j + 1, cache, index + 1, charWord);
        backTrack(board, i, j - 1, cache, index + 1, charWord);
        //hashSet为可变结构，一定要回溯到之前的状态
        cache.remove(i * board[0].length + j);
    }
}

• 单词拆分
  给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

例子1

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

例子2

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

代码如下

class Solution {
    boolean flag;
    HashSet<String> cache;
    public boolean wordBreak(String s, List<String> wordDict) {
        cache = new HashSet<>();
        backTrack(wordDict,s,new StringBuffer());
        return flag;
    }

    public void backTrack(List<String> wordDict,String s,StringBuffer x){
        //由于s是String类型，而x是StringBuffer类型，所以不能直接使用equals()进行比较
        //需要将x转化为String类型，有俩种方式
        //1. new String(x)
        //2. x.toString()
        if(s.equals(new String(x))){
            flag =true;
            return;
        }
        //如果x的长度大于s且不俩不相同时返回false
        if(x.length()>s.length()){
            return;
        }
        //如果该x已经访问过，则直接return
        if(cache.contains(x)){
            return;
        }
        //使用备忘录方式:这里有个特别需要注意的点：需要将可变类型的 StringBuffer 转化为不可变类型的字符串类型
        // String 才能加入到 HashSet 中进行判断，因为 HashSet 中判断元素是否相同是通过 hashCode() 和 equals()
        // 进行判断的，而 StringBuffer 类型并没有重写 hashCode() 和 equals() 方法，所以加入到 HashSet 中后，判断时会出现错误
        //也就是说hashSet和hashMap中不能使用StringBuffer类型，必须转化为String类型
        cache.add(x.toString());
        //此题可发现，有点类似完全背包，但是是要求取出元素顺序的，所以每次循环wordDict的所有元素，一次拼接
        for (int i=0;i<wordDict.size();i++){
            //x属于StringBuffer，属于可变类型，所以在append之后一定要delete
            x.append(wordDict.get(i));
            //这里还使用了一个小技巧，在append之后其实我们就可以判断是否满足条件
            //判断append之后的x是否和s的0到x.length()-1都相同，如果相同可继续遍历，如果不能则不需要继续遍历了
            if(x.length()<=s.length() && compare(s,x)){
                backTrack(wordDict,s,x);
            }
            //delete(start,end),start是删除位置的起始下标，end-1是结束下标不包括end下标，这点一定要注意
            x.delete(x.length()-wordDict.get(i).length(),x.length());
        }
        cache.remove(x.toString());
    }

    /**
     * 判断x是否和s前置字符串相同
     */
    public boolean compare(String s,StringBuffer x){
        if(s.substring(0,x.length()).equals(x.toString())) return true;
        return false;
    }
}

• 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

实例1

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

实例2

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

代码如下

class Solution {
    int maxMoney;
    HashMap<Integer,Integer> cahce;
    public int rob(int[] nums) {
        cahce = new HashMap<>();
        maxMoney(nums,0,0);
        return maxMoney;
    }

    /**
     * 表示到index时还没决定是否抢index时，身上所抢的金额
     * @param nums
     * @param index 
     * @param money 
     */
    public void maxMoney(int[] nums,int index,int money)
    {
        if(index>= nums.length){
            maxMoney = Math.max(maxMoney,money);
            return;
        }
        //如果到index时，当前所抢的金额小于历史所抢的金额，那就直接返回
        if(cahce.containsKey(index) && money < cahce.get(index)){
            return;
        }
        //记录当前index时，身上所抢的金额
        cahce.put(index,money);
        //抢劫index，所以只能抢劫index+2
        maxMoney(nums,index+2,money+nums[index]);
        //不抢劫index，则可以抢劫index+1
        maxMoney(nums,index+1,money);
        cahce.remove(index);
    }
}