leetcode62-Unique Paths

2024-06-04 07:36
文章标签 paths unique leetcode62

本文主要是介绍leetcode62-Unique Paths,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
示例 1:
输入:m = 3, n = 7
输出:28

分析

每次只能向下或者向右,我们可以用dp[i][j]表示走到当前的路径,那么dp公式就可以为dp[i][j]=dp[i-1][j]+dp[i][j-1] ,最后注意起始条件,即第一行和第一列的路径数只能是1

public class uniquePaths {public static void main(String[] args) {System.out.println(getUniquePath(3,7));}public static int getUniquePath(int m,int n) {int[][] dp = new int[m][n];for(int i = 0;i<m;i++) {dp[i][0] = 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];}
}

这篇关于leetcode62-Unique Paths的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1029457

相关文章

大数据Java基础-JAVA IO 9】java IO流 (九) Path、Paths、Files的使用

1.NIO的使用说明: >Java NIO (New IO,Non-Blocking IO)是从Java 1.4版本开始引入的一套新的IO API,可以替代标准的Java IO AP。 >NIO与原来的IO同样的作用和目的,但是使用的方式完全不同,NIO支持面向缓冲区的(IO是面向流的)、基于通道的IO操作。 >NIO将以更加高效的方式进行文件的读写操作。 >随着 JDK 7 的发布,Java对N

LeetCode 63 Unique Paths II

题意: 给出一个带有障碍物的棋盘,每次行动向下或向右移动一格,求从左上角到右下角有几种方案。 思路: 简单dp题,假设dp[i][j]表示第i行第j列的方案数,那么状态转移方程就为 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 。 注意下边界条件就好了,而且对于障碍物,直接把dp清零即可。 可以发现这个dp只和当前行和上一行有关,进而做空间优化,用一

LeetCode 62 Unique Paths

题意: 一个n*m的棋盘,每次行动只能向下或者向右走1格,求从左上角走到右下角有几种不同的方案数。 思路: 因为行动只能向下向右,所以总步数是一定的,即n - m + 2步。那么问题就变成了这里面的哪几步是向下的,就是组合数了,即从n - m + 2个中选n - 1个的组合数。 题目里说的n和m值太夸张了,因为他的函数返回int……所以肯定很小。 代码: class S

Unique Email Address

思路1:面试的时候可以自己写process method class Solution {public int numUniqueEmails(String[] emails) {if(emails == null || emails.length == 0) {return 0;}HashSet<String> set = new HashSet<String>();for(String

C++ boost::upgrade_lock boost::upgrade_to_unique_lock如何使用 例子

upgrade_lock将可将读锁(shared_lock)升级为upgrade_lock,与shared_lock不互斥,与别的upgrade_lock和unique_lock互斥。 也就是说线程A获得mutex的upgrade_lock后,线程B、C等还可以获得mutex的share_mutex,反之亦然。 upgrade_to_unique_lock可将upgrade_lock升级为独占

C++ 有 mutex.lock 为什么要用 lock_guard 、unique_lock

因为直接操作 mutex,即直接调用 mutex 的 lock / unlock 函数。   而使用 lock_guard 可以自动加锁、解锁   C++ Boost库 多线程 线程锁mutex lock_guard 、unique_lock 实例_软件工程小施同学 的专栏-CSDN博客

【C++11及其特性】智能指针——unique_ptr

unique_ptr目录 一.排他所有权模式二.auto_ptr的缺点1.可以直接复制和拷贝构造2.STL可以直接赋值3.不支持动态内存分配数组 三.unique_ptr(C++11)1.不支持直接赋值和构造2.STL可以不可以直接赋值3.支持动态内存分配数组 四.unique_ptr的用法1.构造函数2.赋值操作3.主动释放对象4.放弃对象控制权5.重置6.交换 五.排他性智能指针的陷阱六

【C++】智能指针——auto_ptr,unique_ptr,shared_ptr

目录 auto_ptr unique_ptr shared_ptr 并发问题 循环引用问题 个人主页:传送门——>东洛的克莱斯韦克 智能指针的原理:传送门——>智能指针的原理 auto_ptr 使用方法参考官方文档 传送门——>auto_ptr文档 auto_ptr并不是一个优秀的智能指针,它的设计理念是——管理权转移。如下代码示意 auto_ptr(aut

代码随想录算法训练营第三十九天| LeetCode62.不同路径、LeetCode63.不同路径II、LeetCode343. 整数拆分

#LeetCode 62. Unique Path #LeetCode 62. 视频讲解:动态规划中如何初始化很重要!| LeetCode:62.不同路径_哔哩哔哩_bilibili 动态规划五部曲: 1. 确定dp[i][j] 的含义,在这里dp[i][j] 代表第i, j 位置的路径数目 2. 递推公式,题目规定,移动的方向只能是右方或者下方,所以当前位置i, j 的路径数目只能