带黑名单的网格路径计数问题：冗余路径记忆化优化问询

你的递归解法之所以是指数级时间，核心问题是大量重复计算了相同的子问题——比如不同的路径走到同一个单元格(r,c)时，都会重新递归计算一遍到这个单元格的路径数，完全没必要嘛！咱们用记忆化缓存来解决这个问题，思路很简单：把已经算过的单元格路径数存起来，下次再用到直接取就行。

具体优化步骤 #

• 新增一个和网格同尺寸的记忆化数组memo，初始值设为-1（用来标记这个单元格还没计算过，因为路径数可能是0，不能用0当标记）
• 在递归函数里先查缓存：如果memo[r][c]不是-1，直接返回这个值，不用再递归了
• 处理边界和不可通行的情况：
  • 如果到了起点(0,0)，路径数就是1（只有自己到自己这一条）
  • 如果越界（r或c小于0），或者当前单元格是黑名单（不可通行），路径数就是0
• 正常情况的话，当前单元格的路径数等于从上方下来的路径数加上从左方过来的路径数，计算完把结果存到memo里再返回

优化后的Java代码示例 #

// 记忆化缓存，需要在调用count前初始化
int[][] memo;

int count(boolean[][] array, int r, int c) {
    // 先查缓存，避免重复计算
    if (memo[r][c] != -1) {
        return memo[r][c];
    }
    
    // 起点的情况：只有1条路径
    if (r == 0 && c == 0) {
        return memo[r][c] = 1;
    }
    
    // 越界或者当前单元格不可通行，返回0
    if (r < 0 || c < 0 || array[r][c]) {
        return memo[r][c] = 0;
    }
    
    // 递归计算上方和左方的路径总和
    int totalPaths = count(array, r - 1, c) + count(array, r, c - 1);
    // 把结果存入缓存
    memo[r][c] = totalPaths;
    return totalPaths;
}

// 初始化缓存的代码（调用count之前执行）
// memo = new int[array.length][array[0].length];
// for (int i = 0; i < array.length; i++) {
//     Arrays.fill(memo[i], -1);
// }

优化后的复杂度 #

时间复杂度直接降到了O(r*c)——每个单元格只会被计算一次，再也没有重复递归的开销。空间复杂度是O(r*c)，主要是缓存数组的占用，如果想要进一步优化空间，还可以改成迭代式的动态规划，用一维数组来存，但记忆化递归的方式和你原来的代码结构最接近，改起来最省心。

另外要注意：确认下你的array数组里，true是不是代表不可通行的黑名单单元格，如果是false的话，要把判断条件改成!array[r][c]哦。

内容的提问来源于stack exchange，提问作者rgamber