m*n矩阵到右下角所有路径生成Java代码逻辑解析求助

public static int printStepsToReachBottom(int rows, int columns, String[] array) {
    if (rows == 1) {
        array[0] = "";
        for (int i = 0; i < columns - 1; i++) {
            array[0] += "H";
        }
        return 1;
    }
    if (columns == 1) {
        array[0] = "";
        for (int i = 0; i < rows - 1; i++) {
            array[0] += "V";
        }
        return 1;
    }
    String[] temporary = new String[1000];
    int k = 0;
    int firstTypeMove = printStepsToReachBottom(rows - 1, columns, array);
    for (int i = 0; i < firstTypeMove; i++) {
        temporary[k] = array[i] + "V";
        k++;
    }
    int secondTypeMove = printStepsToReachBottom(rows, columns - 1, array);
    for (int i = 0; i < secondTypeMove; i++) {
        temporary[k] = array[i] + "H";
        k++;
    }
    for (int i = 0; i < secondTypeMove + firstTypeMove; i++) {
        array[i] = temporary[i];
    }
    return secondTypeMove + firstTypeMove;
}
public static void main(String[] args) {
    String[] array = new String[1000];
    int outputSize = printStepsToReachBottom(2, 2, array);
    for (int i = 0; i < outputSize; i++) {
        System.out.println(array[i]);
    }
}

这段代码解决的是 m行n列网格中，从左上角起点到右下角终点，仅允许向右（缩写H，Horizontal）、向下（缩写V，Vertical）移动的所有路径枚举 问题，核心采用分治递归思路实现。

1. 递归终止条件 #

当网格退化为边界场景时，只有唯一可行路径，直接返回结果：

• 若rows == 1：仅剩1行，无法再向下移动，只能全程向右走，路径由columns-1个H拼接而成，返回1表示仅1种路径
• 若columns == 1：仅剩1列，无法再向右移动，只能全程向下走，路径由rows-1个V拼接而成，返回1表示仅1种路径

2. 递归拆解逻辑 #

任意非边界的rows*columns网格的所有路径，可拆分为互不重叠的两类：

• 第一类：第一步先向下走1步，剩余问题转化为求(rows-1)*columns网格的所有路径，把这部分所有路径末尾拼接V，就是第一类路径的全部结果
• 第二类：第一步先向右走1步，剩余问题转化为求rows*(columns-1)网格的所有路径，把这部分所有路径末尾拼接H，就是第二类路径的全部结果
  两类路径合并后就是当前网格的全部可行路径，返回两类路径的总数作为当前层级的结果。

3. 2行2列场景的调用流程 #

以你提到的入参printStepsToReachBottom(2, 2, array)为例，完整执行流程如下：

1. 初始调用2行2列，不满足终止条件，先递归调用printStepsToReachBottom(1, 2, array)
   • 触发rows == 1的终止条件，array[0]被赋值为H，返回路径数1
   • 把H末尾拼接V得到HV，存入临时数组temporary的第0位
2. 接下来递归调用printStepsToReachBottom(2, 1, array)
   • 触发columns == 1的终止条件，array[0]被赋值为V，返回路径数1
   • 把V末尾拼接H得到VH，存入临时数组temporary的第1位
3. 把临时数组中的HV、VH赋值回传入的array数组，返回总路径数2
4. main方法遍历array输出两个路径，和你看到的结果一致。

内容的提问来源于stack exchange，提问作者KaaL-EL