从递归到动态规划（三维）

问题描述

假设有一个三维空间的网格，其大小为 m x n x p。我们从坐标 (0, 0, 0) 出发，要到达坐标 (m - 1, n - 1, p - 1)。每次只能在三个方向上移动：向前（x 坐标加 1）、向右（y 坐标加 1）或向上（z 坐标加 1）。问一共有多少种不同的路径可以到达终点？

1. 递归解法

递归是一种直接根据问题的定义来解决问题的方法。对于这个三维路径问题，我们可以通过递归函数来计算到达终点的路径数。

public class ThreeDimensionalPath {// 递归方法计算路径数public static int recursivePaths(int m, int n, int p) {// 边界条件：如果到达起点，只有一种路径if (m == 0 && n == 0 && p == 0) {return 1;}// 如果越界，返回 0 表示没有路径if (m < 0 || n < 0 || p < 0) {return 0;}// 递归计算从三个方向过来的路径数之和return recursivePaths(m - 1, n, p) + recursivePaths(m, n - 1, p) + recursivePaths(m, n, p - 1);}public static void main(String[] args) {int m = 2, n = 2, p = 2;int paths = recursivePaths(m, n, p);System.out.println("递归方法：从 (0, 0, 0) 到 (" + m + ", " + n + ", " + p + ") 的路径数为: " + paths);}
}

解释：

• 递归函数 recursivePaths 接收三个参数 m、n 和 p，表示目标点的坐标。
• 当到达起点 (0, 0, 0) 时，返回 1，表示有一种路径到达该点。
• 如果越界（即某个坐标小于 0），返回 0，表示没有路径。
• 否则，递归计算从三个方向（(m - 1, n, p)、(m, n - 1, p) 和 (m, n, p - 1)）过来的路径数之和。

缺点：递归方法存在大量的重复计算，时间复杂度非常高，为 O(3的m+n+p次方)，因为每次递归调用都会产生三个新的递归调用。

2. 三维动态规划解法

动态规划是一种通过保存子问题的解来避免重复计算的方法。对于这个三维路径问题，我们可以使用一个三维数组来保存中间结果。

public class ThreeDimensionalPath {// 三维动态规划方法计算路径数public static int dpPaths(int m, int n, int p) {// 创建一个三维数组来保存中间结果int[][][] dp = new int[m + 1][n + 1][p + 1];// 初始化起点的路径数为 1dp[0][0][0] = 1;// 填充三维数组for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {for (int k = 0; k <= p; k++) {if (i > 0) {dp[i][j][k] += dp[i - 1][j][k];}if (j > 0) {dp[i][j][k] += dp[i][j - 1][k];}if (k > 0) {dp[i][j][k] += dp[i][j][k - 1];}}}}// 返回终点的路径数return dp[m][n][p];}public static void main(String[] args) {int m = 2, n = 2, p = 2;int paths = dpPaths(m, n, p);System.out.println("三维动态规划方法：从 (0, 0, 0) 到 (" + m + ", " + n + ", " + p + ") 的路径数为: " + paths);}
}

解释：

• 首先，创建一个三维数组 dp，其大小为 (m + 1) x (n + 1) x (p + 1)，用于保存从起点到每个点的路径数。
• 初始化起点 (0, 0, 0) 的路径数为 1。
• 然后，使用三重循环遍历三维数组，对于每个点 (i, j, k)，如果 i > 0，则加上从 (i - 1, j, k) 过来的路径数；如果 j > 0，则加上从 (i, j - 1, k) 过来的路径数；如果 k > 0，则加上从 (i, j, k - 1) 过来的路径数。
• 最后，返回终点 (m, n, p) 的路径数。

优点：动态规划方法避免了重复计算，时间复杂度为 O(m∗n∗p)，空间复杂度也为 O(m∗n∗p)。

相应题目链接

474. 一和零 - 力扣（LeetCode）

879. 盈利计划 - 力扣（LeetCode）

688. 骑士在棋盘上的概率 - 力扣（LeetCode）

2435. 矩阵中和能被 K 整除的路径 - 力扣（LeetCode）

87. 扰乱字符串 - 力扣（LeetCode）