一、题目描述
======
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
示例1:
输入:m = 3, n = 7 输出:28 示例 2:
输入:m = 3, n = 2 输出:3 解释: 从左上角开始,总共有 3 条路径可以到达右下角。
向右 -> 向下 -> 向下 向下 -> 向下 -> 向右 向下 -> 向右 -> 向下 示例 3:
输入:m = 7, n = 3 输出:28 示例 4:
输入:m = 3, n = 3 输出:6
二、思路分析
======
转移方程
dp[i][j]
来表示从地图左上角做到地图(i,j)位置的情况dp[i][j]
的值了dp[i][j]\=dp[i−1][j]+dp[i][j−1]dp[i][j]=d p[i-1][j]+d p[i][j-1]dp[i][j]\=dp[i−1][j]+dp[i][j−1]
dp[i][j]
表示一个虚拟空间地址时他的值等于0。初始值
dp[0][0]=1
。这里理解可能有点抽象。dp[0][0]
在左上角是无法通过下移或者右移来实现的,因为他就是原地踏步才可以。这有点和题意不符。dp[0][1]=dp[0][0]
.。 所以dp[0][0]=1
.dp[0][0]=1
从小到大执行
三、AC 代码
=======
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
dp[0][0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) {
continue;
}else if (i == 0) {
dp[i][j] = dp[i][j - 1];
} else if (j == 0) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m-1][n-1];
}
升级
--
(m-1)+(n-1)
, 所以我们只需要在m-2
中找出m-1
中可能就行了。 下面贴出一张官网的公式推倒Cm+n−2m−1\=(m+n−2m−1)\=⟨m+n−2}(m+n−3)⋯n(m−1)!\=(m+n−2)!(m−1)!(n−1)!C_{m+n-2}^{m-1}=\left(\begin{array}{c} m+n-2 \\ m-1 \end{array}\right)=\frac{\langle m+n-2\}(m+n-3) \cdots n}{(m-1) !}=\frac{(m+n-2) !}{(m-1) !(n-1) !}Cm+n−2m−1\=(m+n−2m−1)\=(m−1)!⟨m+n−2}(m+n−3)⋯n\=(m−1)!(n−1)!(m+n−2)!
四、总结
====
我正在参与2023腾讯技术创作特训营第三期有奖征文,组队打卡瓜分大奖!
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。