题目
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思考
- 1、有几种方式=》可以重上面进行推到=》使用动态规划
- 2、每一个dp下标表示的是，我到这个点有几种方式
代码和注释
/**
动态规划
1、下标的意义：dp[i][j] 表示的时到每个一点有几种方式
2、动态方程：dp[i][j] = dp[i-1][j] + dp[i][j - 1](当前的点只能，从上一个点或者左边一个点过来)
3、初始化=》最左边一列，和最右边一列
4、遍历顺序
5、log
*/
class Solution {
public int uniquePaths(int m, int n) {
// 动态数组
int[][] dp = new int[m][n];
// 初始化(最左边只有一种，最上面也只有一种)
for(int i = 0; i < m; i++){
dp[i][0] = 1;
}
for(int j = 0; j < n; j++){
dp[0][j] = 1;
}
// 遍历
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、行列式：双重循环
- 2、初始化，顶部的列和左侧的列只有一种方式，从左边过来或者从右边过来
- 3、遍历的时候，是从左上角到右下角。行列式中使用双重循环
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/96116.html
