剑指offer.12.矩阵中的路径之回溯、DFS剪枝的通俗理解

矩阵中的路径

• 前言
• 一、DFS回溯+剪枝
• • 1、源码
• 总结

前言

经常看到动态规划专业名称，其实就是找规律，根据规律来不断更新（动态规划里叫状态转移）自己想要的结果（动态规划里叫返回值）。这里的不断就是动态，根据规律更新就是规划，所以叫动态规划。

用题来刨析动态规划的四个方面

今天自己把这个题做了，看了别人用专业术语讲解才知道自己使用的一些常规方法原来对应着这些专业名称。

1）回溯，就是在遇到递归到出口时，会返回上一次自己被调用的位置，利用递归栈倒序释放这一过程。称之为回溯，其实就是利用函数栈释放这一过程中来完成自己想要的任务。

2）剪枝，就是递归过程中，若有不符合继续递归下去的条件时，就不必要再继续下去了。一般用这些条件设置一些递归出口。

一、DFS回溯+剪枝

通过4个方向的DFS+剪枝试探，来判断从一个字符出发，是否有已给路径。

1、源码

public class Exist12 {
    int[][] visited;
    int wordlen;
    String s;

    public boolean exist(char[][] board, String word) {
        //维持一个访问矩阵，通过递归来寻找是否存在这样的序列。、
        //特殊情况直接返回
        if (word.length() == 0)
            return true;
        if (board.length == 0 || board[0].length == 0)
            return false;
        //初始化
        visited = new int[board.length][board[0].length];
        wordlen = word.length();
        s = word;
        //从每一个字符出发
        for (int i = 0; i < board.length; i++)
            for (int j = 0; j < board[0].length; j++) {
                if (recursion(board, i, j, 0))
                    return true;
            }
        //所有字符开始都没找到已给路径。
        return false;
    }
    //DFS+剪枝
    public boolean recursion(char[][] board, int i, int j, int nextc) {
        //完成所有字符的比较，都没有返回false，这里就返回true，一个递归出口
        if (nextc == wordlen)
            return true;
        //不可能的一些情况就直接剪枝
        if (i == -1 || j == -1 || i == board.length || j == board[0].length || visited[i][j] == 1 || board[i][j] != s.charAt(nextc))
            return false;
        //走过的路径，把访问标记设为1
        visited[i][j] = 1;
        if (recursion(board, i - 1, j, nextc + 1) || recursion(board, i + 1, j, nextc + 1) || recursion(board, i, j + 1, nextc + 1) || recursion(board, i, j - 1, nextc + 1))
            return true;
        //走不同的路径把访问标记还原，并返回失败false
        visited[i][j] = 0;
        return false;
    }
}
           

总结

熟练掌握递归是解决这些搜索问题的一大基石。

1）时间复杂度，O(3LMN)，MN代表每一个字符开始，L表示word的长度，3表示有没走一步有三种选择。

2）空间复杂度，O(MN)，递归栈最大为L，L<<MN。