题目英文
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?
Above is a 7 x 3 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
Example 1:
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right
Example 2:
Input: m = 7, n = 3
Output: 28
题目中文
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
问总共有多少条不同的路径?
例如,上图是一个7 x 3 的网格。有多少可能的路径?
说明:m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
示例 3:
输入: m = 23, n = 12
输出: 193536720
算法实现
方式一:利用递归
public class Solution
{private int _m;private int _n;public int UniquePaths(int m, int n){_m = m;_n = n;int count = 0;RecordPaths(0, 0, ref count);return count;}private void RecordPaths(int i, int j, ref int count){if (i == _m - 1 && j == _n - 1){count++;return;}if (i < _m){RecordPaths(i + 1, j, ref count);}if (j < _n){RecordPaths(i, j + 1, ref count);}}
}
使用递归的方式,容易理解但会耗费大量的时间,所以在运行 示例3 的时候,超时了。
方式二:利用动态规划
动态规划表格01:
动态规划表格02:
动态规划的最优子结构为:d[i,j] = d[i-1,j] + d[i,j-1]
public class Solution
{public int UniquePaths(int m, int n){int[,] memo = new int[m, n];for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (i == 0){memo[i, j] = 1;}else if (j == 0){memo[i, j] = 1;}else{memo[i, j] = memo[i - 1, j] + memo[i, j - 1];}}}return memo[m - 1, n - 1];}
}
实验结果
- 状态:通过
- 62 / 62 个通过测试用例
- 执行用时: 52 ms, 在所有 C# 提交中击败了 93.18% 的用户
- 内存消耗: 13.6 MB, 在所有 C# 提交中击败了 17.65% 的用户
相关图文
1. “数组”类算法
- LeetCode实战:三数之和
- LeetCode实战:最接近的三数之和
- LeetCode实战:求众数
- LeetCode实战:缺失的第一个正数
- LeetCode实战:快乐数
- LeetCode实战:寻找两个有序数组的中位数
- LeetCode实战:盛最多水的容器
- LeetCode实战:删除排序数组中的重复项
- LeetCode实战:搜索旋转排序数组
- LeetCode实战:螺旋矩阵
2. “链表”类算法
- LeetCode实战:两数相加
- LeetCode实战:删除链表的倒数第N个节点
- LeetCode实战:合并两个有序链表
- LeetCode实战:合并K个排序链表
- LeetCode实战:两两交换链表中的节点
- LeetCode实战:旋转链表
- LeetCode实战:环形链表
3. “栈”类算法
- LeetCode实战:有效的括号
- LeetCode实战:最长有效括号
- LeetCode实战:逆波兰表达式求值
4. “队列”类算法
- LeetCode实战:设计循环双端队列
- LeetCode实战:滑动窗口最大值
- LeetCode实战:整数反转
- LeetCode实战:字符串转换整数 (atoi)
5. “递归”类算法
- LeetCode实战:爬楼梯
6. “字符串”类算法
- LeetCode实战:反转字符串
- LeetCode实战:翻转字符串里的单词
- LeetCode实战:最长公共前缀
- LeetCode实战:字符串相加
- LeetCode实战:字符串相乘
7. “树”类算法
- LeetCode实战:相同的树
- LeetCode实战:对称二叉树
- LeetCode实战:二叉树的最大深度
- LeetCode实战:将有序数组转换为二叉搜索树
8. “哈希”类算法
- LeetCode实战:两数之和
9. “搜索”类算法
- LeetCode实战:搜索二维矩阵
10. “动态规划”类算法
- LeetCode实战:最长回文子串
- LeetCode实战:最大子序和
11. “回溯”类算法
- LeetCode实战:全排列
11. “数值分析”类算法
- LeetCode实战:回文数
- LeetCode实战:x 的平方根