关于9-9，记忆化搜索

Question

老师您好！关于9-9实现leetcode上980号问题，事实上我自己写了一份代码，也通过了测试，但是对于我这套代码的记忆化搜索写法，我并不是很清楚，也不确定能否在不改变代码结构和dfs函数返回值的基础上实现记忆化搜索，想请您帮忙看看；
具体思路是这样的：与您的写法只有一点不同，就是dfs没有返回值，而我另外选择一个全局变量cnt计数路径数目

//leetcode 980

class Solution1 {
    private int[][] grid;
    private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private int R, C;
    private int sour = -1, dest = -1;//起点坐标和终点坐标，将二维映射到一维后的结果
    private int numOfZero = 0;
    private int cnt = 0;//记录哈密尔顿路径数目的变量
    public int uniquePathsIII(int[][] grid) {
        this.grid = grid;
        R = grid.length;
        C = grid[0].length;

        for(int i = 0; i < R; i ++)
            for(int j = 0; j < C; j ++) {
                if (grid[i][j] == 1)
                    sour = i*C + j;
                else if (grid[i][j] == 2)
                    dest = i*C + j;
                if(grid[i][j] != -1)
                    numOfZero ++;
            }
        if(sour == -1 || dest == -1) return 0;

        int visited = 0;
        dfs(visited, sour / C, sour % C, numOfZero);//一张图的结点个数固定，哈密尔顿路径需遍历所有节点
        return cnt;
    }

    private void dfs(int visited, int x, int y, int left){//left变量记录剩余的应遍历的结点数
        visited += (1 << (x*C+y));
        left --;
        if(left == 0 && x*C + y == dest)
            cnt++;//找到一条路径
        else {
            for (int d = 0; d < 4; d++) {//遍历v的所有邻点
                int netx = x + dirs[d][0], nety = y + dirs[d][1];
                int next = netx*C + nety;
                if (inArea(netx, nety) && (visited & (1<<next)) == 0 && grid[netx][nety] != -1)
                    dfs(visited, netx, nety, left);
            }
        }
    }
    private boolean inArea(int x, int y){return x >= 0 && x < R && y >= 0 && y < C;}
}

对于我这个dfs的写法，没有返回任何类型，所以递归函数语义可能相对比较模糊；没有记录每个(visited， v)数值对可以到达终点的路径数目，所以感觉上应该不能使用 "int[][]"型数组来存储这个历史；那么能否使用别的方法来实现这个代码上的记忆化搜索呢？

Answer 1

liuyubobobo 2019-09-22 15:02:58

我可能没有特别理解你的问题。你的这个代码并不是记忆化搜索，就是回溯法：）

继续加油！：）

• 提问者 martin123_ #1

  是啊，我的意思是如何在这个代码基础上加上记忆化搜索的机制

• 提问者 martin123_ #2

  然后我尝试用您课程里面讲的memo数组去试了一下，但是我自己写不出那个逻辑，可能是因为dfs函数语义不到位

• liuyubobobo 回复 提问者 martin123_ #3

  visited, x, y 合在一起构成了一个状态。状态定义和课程中是一样的。如果没有返回值，就不能写出记忆化搜索，因为记忆化搜索就是要为状态赋值。你的结果相当于使用全局变量记录了。

点开查看后面1条评论