力扣:62. 不同路径

devtools/2025/3/19 11:31:33/

62. 不同路径

一个机器人位于一个 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 * 109

1、动态规划

class Solution {public int uniquePaths(int m, int n) {if(m<=1||n<=1)return 1;//排除行列为1的情况int[][] dp = new int[m][n];//定义dp数组为某行某列达到的路径数for(int i = 0;i < m;i++){dp[i][0] = 1;//初始化数组,第一行第一列的路径数都是1}for(int i = 0;i < n;i++){dp[0][i] = 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];//返回右下角的路径数}
}

2、卡尔的数论解法

class Solution {
public:int uniquePaths(int m, int n) {long long numerator = 1; // 分子int denominator = m - 1; // 分母int count = m - 1;int t = m + n - 2;while (count--) {numerator *= (t--);while (denominator != 0 && numerator % denominator == 0) {numerator /= denominator;denominator--;}}return numerator;}
};作者:代码随想录
链接:https://leetcode.cn/problems/unique-paths/solutions/2562792/dai-ma-sui-xiang-lu-leetcode62bu-tong-lu-ncye/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


http://www.ppmy.cn/devtools/34453.html

相关文章

文件批量改名字怎么改(怎样批量修改文件名)

文件批量改名字怎么改&#xff08;怎样批量修改文件名&#xff09; 批量重命名文件可以通过多种方法实现&#xff0c;具体取决于用户的操作系统和熟练程度。 以下是一些常见的方法&#xff1a; 下载地址https://download.csdn.net/download/dhyuan_88/89237041 使用操作系统自带…

WP Rocket插件下载:加速您的WordPress网站,提升用户体验

在互联网速度决定用户体验的今天&#xff0c;一个快速加载的网站对于吸引和保留访问者至关重要。WP Rocket插件&#xff0c;作为一款专为WordPress设计的高性能缓存插件&#xff0c;提供了一套完整的解决方案&#xff0c;帮助您优化网站性能&#xff0c;提升用户体验。 [WP Ro…

QT图片图标更改后不加载问题处理

QT通过setPixmap、setIcon、setMovie等方法&#xff0c;设置图片、图标时&#xff0c;会更新图片、图标函数执行&#xff0c;但是图片图标并没有更改的情况。 尝试通过信号槽方式去设置图片&#xff0c;仍然不能响应更改&#xff0c;以下提供一个可行的解决方法。 在setPixma…

【Python深度学习(第二版)(4)】神经网络的基本数据结构-张量概念、阶数、使用NumPy操作张量、张量种类、样本轴等概念

文章目录 一. 张量概念二. 张量的阶数1. 标量&#xff08;0阶张量&#xff09;2. 向量&#xff08;1阶张量&#xff09;2. 矩阵&#xff08;2阶张量&#xff09;3. 3阶张量与更高阶的张量 三. 张量属性及操作张量1. 张量的关键属性2. 在NumPy中操作张量2.1. 选择某个图片数据2.…

代码随想录算法训练营day60

647. 回文子串 五部曲&#xff1a; dp数组下标及含义&#xff1a; dp[i][j]&#xff1a;表示区间范围[i,j] 的子串是否是回文子串&#xff0c;如果是dp[i][j]为true&#xff0c;否则为false。 dp数组初始化&#xff1a; dp[i][j]初始化为false。 递推公式&#xff1a; s[…

人工智能|推荐系统——工业界的推荐系统之交叉

Factorized Machine 线性模型预测是特征的加权和。(只有加,没有乘。) 二阶特征交叉 可以通过矩阵分解减少模型参数量 深度交叉网络(DCN) 之前提到过的召回、排序模型中的神经网络可以用任意网络结构;常见的交叉层

2024年开视频号小店需要什么条件?多少资金?一篇详解!

大家好&#xff0c;我是电商糖果 2024年只要你想创业做电商&#xff0c;或者想找副业项目&#xff0c;我想很多人都会给你推荐视频号小店。 为什么&#xff1f; 视频号小店是微信视频号推出的电商平台&#xff0c;因为它背后有着十几亿的真实用户&#xff0c;以及无法预估的…

【信息安全管理与评估】某年“信息安全管理与评估”第二阶段:Windows应急响应例题

文章目录 1、提交攻击者的IP地址&#xff1b;2、识别攻击者使用的操作系统&#xff1b;3、找出攻击者资产收集所使用的平台&#xff1b;4、提交攻击者目录扫描所使用的工具名称&#xff1b;5、提交攻击者首次攻击成功的时间&#xff0c;格式&#xff1a;DD /MM/YY:HH:MM:SS&…