一、题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7 输出：28
示例 2：
输入：m = 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3 输出：28
示例 4：
输入：m = 3, n = 3 输出：6
提示：
1 <= m, n <= 100- 题目数据保证答案小于等于
2 * 10^9
二、解题思路
- 动态规划的理解：动态规划是一种通过将复杂问题分解为更小的子问题来解决问题的方法。在这个问题中，我们可以将网格划分为更小的子网格，并找出每个子网格到达右下角的不同路径数量。
- 状态定义：定义dp[i][j]为从左上角到达网格第i行第j列的不同路径数量。
- 状态转移方程：对于每一个位置(i, j)，我们可以从上方(i-1, j)或者左方(i, j-1)到达。因此，dp[i][j]的值可以通过dp[i-1][j]（上方来的路径数）加上dp[i][j-1]（左方来的的路径数）得到。
- 初始化：dp[0][j]和dp[i][0]都是1，因为无论在网格的哪一行或哪一列，到达第一个点都只有一种方法。
- 计算顺序：按照行和列的顺序计算dp数组，每次计算都依赖于之前计算的结果。
- 结果：dp[m-1][n-1]即为所求，即从左上角到右下角的不同路径数量。
三、具体代码
class Solution {
public int uniquePaths(int m, int n) {
// 创建一个(m x n)的二维数组用于存储路径数量
int[][] dp = new int[m][n];
// 初始化dp数组的第一行和第一列
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n; j++) {
dp[0][j] = 1;
}
// 按行按列填充dp数组
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
// 状态转移方程
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
// 返回右下角的路径数量
return dp[m-1][n-1];
}
}四、时间复杂度和空间复杂度
1. 时间复杂度
- 代码中的三层循环结构决定了时间复杂度。
- 最外层循环遍历了m行，中间层循环遍历了n列，内层循环则是常数时间的操作。
- 因此，总的操作次数是m乘以n，即O(m * n)。
2. 空间复杂度
- 代码中创建了一个m乘以n的二维数组dp来存储每个子问题的解。
- 这个数组的空间需求是O(m * n)。
- 由于这是算法中唯一的额外空间消耗，所以空间复杂度是O(m * n)。
五、总结知识点
-
动态规划（Dynamic Programming）: 动态规划是一种算法设计技术，它将一个复杂问题分解为更小的子问题，并存储这些子问题的解，以避免重复计算。这种方法通常用于解决具有重叠子问题和最优子结构特性的问题。
-
状态定义: 在动态规划中，我们需要定义状态以及如何通过子问题的解来构建问题的解。在这个问题中，
dp[i][j]表示从网格的左上角到位置(i, j)的不同路径数量。 -
状态转移方程: 状态转移方程是动态规划中的核心，它定义了如何从一个或多个较小的子问题的解来构造当前问题的解。在这段代码中，状态转移方程是
dp[i][j] = dp[i-1][j] + dp[i][j-1]，表示到达当前位置的路径数量是从上方和左方到达的路径数量之和。 -
初始化: 在开始动态规划之前，我们需要初始化一些基础情况，这些情况通常是问题的起始点或者边界条件。在这段代码中，我们初始化了网格的第一行和第一列为1，因为从起点到这些位置只有一条路径。
-
迭代计算: 通过嵌套循环，我们按行按列地计算
dp数组中的每个元素。每次计算都依赖于已经计算过的相邻的上方和左方的元素。 -
二维数组: 代码中使用了二维数组
dp来存储每个位置的路径数量。这是一种常见的数据结构，用于存储和处理网格或矩阵相关的问题。 -
边界处理: 在动态规划中，处理边界条件是非常重要的。在这段代码中，我们特别处理了网格的第一行和第一列，因为这些位置只能从一个方向到达。
六、优化后的代码
虽然代码的空间复杂度是O(m * n)，但实际上我们可以优化到O(n)，因为当我们计算dp[i][j]时，只需要前一行dp[i-1][j]和当前行的dp[i][j-1]的值。
这意味着我们只需要一个一维数组来存储当前行的路径数量，从而将空间复杂度从O(m * n)降低到O(n)，因为每一行只需要一个长度为n的数组。
class Solution {
public int uniquePaths(int m, int n) {
// 创建一个长度为n的一维数组用于存储路径数量
int[] dp = new int[n];
// 初始化dp数组的第一列
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
// 按行填充dp数组
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
// 状态转移方程，只使用前一行的数据
dp[j] = dp[j] + dp[j - 1];
}
}
// 返回最后一列的路径数量
return dp[n - 1];
}
}在这个优化后的代码中，我们只使用了一个一维数组dp，其长度为n。
这样，空间复杂度降低到了O(n)，而时间复杂度仍然是O(m * n)，因为我们需要遍历m行和n列来填充dp数组。
七、优化代码知识点
-
动态规划（Dynamic Programming）: 动态规划是一种解决问题的方法，它将问题分解为更小的子问题，并通过保存子问题的解来避免重复计算。这种方法通常适用于具有重叠子问题和最优子结构的问题。
-
一维数组（1D Array）: 为了优化空间复杂度，代码使用了一维数组
dp而不是二维数组。这个一维数组的长度等于网格的列数n，因为计算下一个位置的路径数量只需要知道当前位置和前一个位置的路径数量。 -
空间复杂度优化: 通过使用一维数组，代码将空间复杂度从
O(m * n)降低到O(n)。这是因为在每一步计算中，我们只需要当前行的路径数量，而不是整个网格的路径数量。 -
状态转移方程（State Transition Equation）: 状态转移方程是动态规划中的核心，它定义了如何从一个或多个较小的子问题的解来构造当前问题的解。在这段代码中，状态转移方程是
dp[j] = dp[j] + dp[j - 1]，表示到达某一列的路径数量是当前位置的路径数量加上前一列的路径数量。 -
初始化: 在开始动态规划计算之前，需要初始化数组的基础状态。在这段代码中，所有位置的初始路径数量被设置为1，因为从网格的左上角开始，到达第一列的每个位置只有一条路径。
-
迭代计算: 通过嵌套循环，代码按行填充
dp数组。每次计算都依赖于前一行的数据，这是动态规划中常见的自底向上的方法。 -
边界处理: 代码中的循环从第二行开始，直到网格的最后一行。这是因为第一行的路径数量已经在初始化阶段设置好了。
-
结果获取: 最后，代码返回
dp数组的最后一个元素，即到达网格右下角的路径数量。由于我们是从左上角到右下角计算路径数量的，所以最终结果存储在数组的最后一个位置。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
