576. 出界的路径数

题目描述

DFS

• 一开始直接用的 DFS 暴搜，结果啪的一交，就 TLE 了

class Solution {
    int m;
    int n;
    int maxMove;
    int startRow;
    int startolum;
    int[] dirx = {-1, 1, 0, 0};
    int[] diry = {0, 0, -1, 1};
    
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        this.m = m;
        this.n = n;
        this.maxMove= maxMove;
        this.startRow= startRow;
        // this.startColumn = startColumn;
        // 深搜
        dfs(startRow, startColumn, 0);
        return res;
    }
    
    int res = 0;
    
    public void dfs(int x, int y, int sum) {
        // 终止条件
        if (x >= m || x < 0 || y >= n || y < 0) {
            if (sum <= maxMove) res++;
            return;
        }
        // 剪枝
        if (sum > maxMove) return;
        for (int i = 0; i < 4; i++) {
            int xx = x + dirx[i];
            int yy = y + diry[i];
            dfs(xx, yy, sum + 1);
        }
    }
}

记忆化搜

后来看了彤哥-题解 发现，要用记忆化搜，记录已经计算过的状态，避免重复计算，提高计算效率

// 彤哥-题解 code
class Solution {

    // 四个方向
    int[][] dirs = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    // 取余
    int MOD = 1000000007;

    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        // 缓存
        int[][][] memo = new int[m][n][maxMove + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k <= maxMove; k++) {
                    memo[i][j][k] = -1;
                }
            }
        }
        return dfs(m, n, maxMove, startRow, startColumn, memo);
    }

    private int dfs(int m, int n, int moveCount, int i, int j, int[][][] memo) {
        // 越界了就找到了一条路径
        if (i < 0 || j < 0 || i >= m || j >= n) {
            return 1;
        }

        // 没有移动次数了，返回0
        if (moveCount == 0) {
            return 0;
        }

        // 缓存中存在
        if (memo[i][j][moveCount] != -1) {
            return memo[i][j][moveCount];
        }

        // 剪枝：如果小球不管怎么移动都无法越出网格，那就剪掉这个枝
        if (i - moveCount >= 0 && j - moveCount >= 0 && i + moveCount < m && j + moveCount < n) {
            return 0;
        }

        // 从这个点出发的符合条件的路径数量
        int sum = 0;
        for (int[] dir : dirs) {
            // 记得取余
            sum = (sum + dfs(m, n, moveCount - 1, i + dir[0], j + dir[1], memo)) % MOD;
        }

        // 记录缓存
        memo[i][j][moveCount] = sum;

        return sum;
    }
}

5852. 最小化目标值与所选元素的差

题目描述

给你一个大小为 m x n 的整数矩阵 mat 和一个整数 target 。

从矩阵的 每一行 中选择一个整数，你的目标是 最小化 所有选中元素之 和 与目标值 target 的 绝对差 。

返回 最小的绝对差 。
a 和 b 两数字的 绝对差 是 a - b 的绝对值。

leetcode 周赛 255 场的第三道题，比赛时 只是想到了 dfs 暴搜（没懂dfs 和 回溯是啥子关系），结果 tle。后来，比赛结束看了题解，有个 python 代码说的是 每行都排序，然后 + 剪枝，但是我试了 依然 tle。最后，看了个 老哥“记忆化”过了

dfs 暴搜（Tle了）

一维棋盘问题

思路

1. for 循环遍历每行的所有列；
2. dfs （即，递归，或者回溯）控制遍历 所有行
3. 遍历完所有行时（终止条件），比较当前 结果是否用更新

class Solution {
    int m = 0;
    int n = 0;
    int minAbsMinus = Integer.MAX_VALUE;

    public int minimizeTheDifference(int[][] mat, int target) {
        if (mat.length == 0) {
            return 0;
        }
        m = mat.length;
        n = mat[0].length;
        backtrack2(mat, target, 0, 0);
        return minAbsMinus;
    }

    /**
     * 二维回溯，棋盘问题。整错了，其实是一维
     * @param mat
     * @param target
     * @param sum
     */
    public void backtrack2(int[][] mat, int target, int row, int sum) {
        // 终止条件
        if (row >= m) {
            // 判断当前 sum 是否要更新
            minAbsMinus = Math.min(minAbsMinus, Math.abs(sum - target));
            return;
        }
        for (int col = 0; col < n; col++) {
            sum += mat[row][col];
            backtrack2(mat, target, row + 1, sum);
            sum -= mat[row][col];
        }
    }

}

一直卡在了，下面这组数据上

排序 + 剪枝（依然 tle）

1. 对 mat 每行按照升序排序；
2. 剪枝

class Solution {
    int m = 0;
    int n = 0;
    int minAbsMinus = Integer.MAX_VALUE;

    public int minimizeTheDifference(int[][] mat, int target) {
        if (mat.length == 0) {
            return 0;
        }
        m = mat.length;
        n = mat[0].length;

         // mat 每一行排序，剪枝
        for (int i = 0; i < m; i++) {
            Arrays.sort(mat[i]);
        }

        backtrack(mat, target, 0, 0);
        return minAbsMinus;
    }

    /**
     * 二维回溯，棋盘问题。整错了，其实是一维
     * @param mat
     * @param target
     * @param sum
     */
    public void backtrack(int[][] mat, int target, int row, int sum) {
        // 终止条件
        if (row >= m) {
            // 判断当前 sum 是否要更新
            minAbsMinus = Math.min(minAbsMinus, Math.abs(sum - target));
            return;
        }
        // 剪枝
        if (sum >= target && sum - target >= minAbsMinus) {
            return;
        }
        for (int col = 0; col < n; col++) {
            sum += mat[row][col];
            backtrack(mat, target, row + 1, sum);
            sum -= mat[row][col];
        }
    }

}

依旧是卡在上面，第 14 组 case 上

记忆化搜

使用记忆化搜，记录之前已经被“计算”过的结果，避免不必要的重复计算

1. 使用 flag[m][5000] 作为 记忆化数组，记录之前已经计算过的结果

   flag[i][sum] 标记第 i 行 总和为 sum 是否已经计算过

2. 每次开始 下层递归之前，判断当前 flag[i][sum] 是否已经记录有值：如果已经有值，说明之前已经计算过，则不必递归；如果没值，再递归

3. 递归开始前（能开始递归表明，当前 flag[i][sum] 没有计算过） ，则标记 flag[i][sum]

class Solution {
    int m = 0;
    int n = 0;
    int minAbsMinus = Integer.MAX_VALUE;
    boolean[][] flag;

    public int minimizeTheDifference(int[][] mat, int target) {
        if (mat.length == 0) {
            return 0;
        }
        n = mat[0].length;
        m = mat.length;
        flag = new boolean[m][5000]; // 记忆化数组

         // mat 每一行排序，剪枝
        for (int i = 0; i < m; i++) {
            Arrays.sort(mat[i]);
        }

        backtrack(mat, target, 0, 0);
        return minAbsMinus;
    }

    /**
     * 二维回溯，棋盘问题。整错了，其实是一维
     * @param mat
     * @param target
     * @param sum
     */
    public void backtrack(int[][] mat, int target, int row, int sum) {
        // 终止条件
        if (row >= m) {
            // 判断当前 sum 是否要更新
            minAbsMinus = Math.min(minAbsMinus, Math.abs(sum - target));
            return;
        }
        // 剪枝 + 记忆化
        if ((sum >= target && sum - target > minAbsMinus) || flag[row][sum]) {
            return;
        }
        // 标记
        flag[row][sum] = true;
        for (int col = 0; col < n; col++) {
            sum += mat[row][col];
            backtrack(mat, target, row + 1, sum);
            sum -= mat[row][col];
        }
    }

}

终于过了，但是题解中 dp 解法更优