每日一题——不同路径的数目与矩阵最小路径和

机器人路径问题与矩阵最小路径和 1. 机器人路径问题题目描述示例示例 1示例 2 解题思路动态规划 代码实现复杂度分析 2. 矩阵的最小路径和题目描述示例示例 1示例 2 解题思路动态规划 代码实现复杂度分析 总结

1. 机器人路径问题 题目描述

一个机器人在 (m \times n) 大小的地图的左上角（起点）。机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。可以有多少种不同的路径从起点走到终点？ 数据范围： (0 < n, m \leq 100)，保证计算结果在 32 位整型范围内。

要求：

空间复杂度：(O(nm))时间复杂度：(O(nm))进阶：空间复杂度 (O(1))，时间复杂度 (O(\min(n, m)))

---

示例 示例 1

输入： 2, 1 返回值： 1

示例 2

输入： 2, 2 返回值： 2

---

解题思路 动态规划

定义状态：

设 dp[i][j] 表示从起点到位置 (i, j) 的不同路径数。

状态转移方程：

机器人只能向下或向右移动，因此： [ dp[i][j] = dp[i-1][j] + dp[i][j-1] ]

边界条件：

当 (i = 1) 或 (j = 1) 时，dp[i][j] = 1，因为只有一条路径（一直向右或一直向下）。

目标：

计算 dp[m][n]，即从起点到终点的路径数。

---

代码实现 #include <stdio.h> #include <stdlib.h> int uniquePaths(int m, int n) { // 分配动态规划表 int** dp = (int**)calloc(m + 1, sizeof(int*)); for (int i = 0; i <= m; i++) { dp[i] = (int*)calloc(n + 1, sizeof(int)); } // 初始化边界条件 for (int i = 1; i <= m; i++) { dp[i][1] = 1; } for (int j = 1; j <= n; j++) { dp[1][j] = 1; } // 填充动态规划表 for (int i = 2; i <= m; i++) { for (int j = 2; j <= n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } // 获取结果 int num = dp[m][n]; // 释放动态规划表 for (int i = 0; i <= m; i++) { free(dp[i]); } free(dp); return num; }

---

复杂度分析 时间复杂度：(O(m \times n))，需要填充 (m \times n) 的动态规划表。空间复杂度：(O(m \times n))，用于存储动态规划表。

---

2. 矩阵的最小路径和 题目描述

给定一个 (n \times m) 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

数据范围： (1 \leq n, m \leq 500)，矩阵中任意值都满足 (0 \leq a_{i,j} \leq 100)。

要求：

时间复杂度：(O(nm))

---

示例

示例 1

输入： [[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]] 返回值： 12

示例 2

输入： [[1,2,3],[1,2,3]] 返回值： 7

---

解题思路 动态规划

定义状态：

设 dp[i][j] 表示从起点到位置 (i, j) 的最小路径和。

状态转移方程：

只能从上方或左方移动，因此： [ dp[i][j] = a[i-1][j-1] + \min(dp[i-1][j], dp[i][j-1]) ]

边界条件：

当 (i = 1) 且 (j = 1) 时，dp[1][1] = a[0][0]。当 (i = 1) 时，只能从左方移动，dp[1][j] = dp[1][j-1] + a[0][j-1]。当 (j = 1) 时，只能从上方移动，dp[i][1] = dp[i-1][1] + a[i-1][0]。

目标：

计算 dp[n][m]，即从起点到终点的最小路径和。

---

代码实现 #include <stdio.h> #include <stdlib.h> int minPathSum(int** matrix, int matrixRowLen, int* matrixColLen) { int m = matrixRowLen; // 行数 int n = *matrixColLen; // 列数 // 分配动态规划表 int** dp = (int**)calloc(m + 1, sizeof(int*)); for (int i = 0; i <= m; i++) { dp[i] = (int*)calloc(n + 1, sizeof(int)); } // 初始化边界条件 for (int i = 0; i <= m; i++) { dp[i][0] = 65535; // 初始化为一个较大的值 } for (int j = 0; j <= n; j++) { dp[0][j] = 65535; // 初始化为一个较大的值 } dp[1][1] = matrix[0][0]; // 特殊处理起点 // 填充动态规划表 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (i == 1 && j == 1) { continue; // 起点已经初始化 } dp[i][j] = matrix[i - 1][j - 1] + ((dp[i - 1][j] < dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1]); } } // 获取结果 int num = dp[m][n]; // 释放动态规划表 for (int i = 0; i <= m; i++) { free(dp[i]); } free(dp); return num; }

---

复杂度分析 时间复杂度：(O(m \times n))，需要填充 (m \times n) 的动态规划表。空间复杂度：(O(m \times n))，用于存储动态规划表。

---

总结 机器人路径问题：通过动态规划计算从起点到终点的路径数。矩阵最小路径和：通过动态规划计算从起点到终点的最小路径和。动态规划是解决路径问题的有效方法，关键在于定义状态和状态转移方程。