当前位置:网站首页>LeetCode#62. Different paths
LeetCode#62. Different paths
2022-07-06 15:21:00 【Rufeng ZHHH】
subject :
A robot is in a m x n The top left corner of the grid ( The starting point is marked as “Start” ).
The robot can only move down or right one step at a time . The robot tries to reach the bottom right corner of the grid ( In the figure below, it is marked as “Finish” ).
Ask how many different paths there are in total ?
Example 1:
Input :m = 3, n = 7
Output :28
Example 2:
Input :m = 3, n = 2
Output :3
explain :
From the top left corner , All in all 3 Path to the bottom right .
1. towards the right -> Down -> Down
2. Down -> Down -> towards the right
3. Down -> towards the right -> Down
Example 3:
Input :m = 7, n = 3
Output :28
Example 4:
Input :m = 3, n = 3
Output :6
Tips :
1 <= m, n <= 100
Question data guarantee that the answer is less than or equal to 2 * 109
source : Power button (LeetCode)
link :62. Different paths - Power button (LeetCode) (leetcode-cn.com)
Method 1 ( Permutation and combination ):
When I first saw this problem, I first thought of it in Mathematics Permutation and combination ( A kind of Combinatorial Mathematics )_ Baidu Encyclopedia (baidu.com), Many high school students must have done this kind of problem , The method is also relatively simple .
Let's assume that we have to go altogether m+n Step , Then just let one of them m Step right , remainder n Step must be down , The calculation is C(m+n,n)=C(m+n,m).
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
son=min(m-1,n-1);mother=m+n-2
up=1;down=1
for i in range(son):
up*=son-i
for i in range(son):
down*=mother-i
if int(down/up)==0:
return 1
else:
return int(down/up)
Method 2 ( Dynamic programming ):
Let's suppose we get to the k Step , Then the general method of the previous steps is the first two k-1 Sum of steps ( From the top left to the bottom right can only be the last step, coming from the left or the top , Otherwise it will be meaningless ), It's just like this in terms of images .
So we need to create a two-dimensional list :
dp=[]
for i in range(m):
dp.append([1]*n) # The default starting values are 1
After creation , It can be calculated according to this idea , This is similar to Yang Hui's Algorithm LeetCode#118. Yang hui triangle _ As the wind Zhhh The blog of -CSDN Blog
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp=[]
for i in range(m):
dp.append([1]*n)
for i in range(m-1):
for j in range(n-1):
dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]
return dp[m-1][n-1]
边栏推荐
- Global and Chinese markets of cobalt 2022-2028: Research Report on technology, participants, trends, market size and share
- JDBC introduction
- 自动化测试你必须要弄懂的问题,精品总结
- Introduction to variable parameters
- Currently, mysql5.6 is used. Which version would you like to upgrade to?
- How to solve the poor sound quality of Vos?
- UCORE lab7 synchronous mutual exclusion experiment report
- UCORE LaB6 scheduler experiment report
- Word macro operation: convert the automatic number in the document into editable text type
- Knowledge that you need to know when changing to software testing
猜你喜欢
Servlet
Video scrolling subtitle addition, easy to make with this technique
Winter vacation daily question - maximum number of balloons
Threads and thread pools
ucore lab5用户进程管理 实验报告
接口测试面试题及参考答案,轻松拿捏面试官
Eigen User Guide (Introduction)
ucorelab4
The maximum number of words in the sentence of leetcode simple question
软件测试行业的未来趋势及规划
随机推荐
Should wildcard import be avoided- Should wildcard import be avoided?
Build your own application based on Google's open source tensorflow object detection API video object recognition system (II)
软件测试工作太忙没时间学习怎么办?
How to become a good software tester? A secret that most people don't know
FSM和i2c实验报告
Mysql database (II) DML data operation statements and basic DQL statements
Servlet
Want to change jobs? Do you know the seven skills you need to master in the interview software test
ArrayList集合
What are the commonly used SQL statements in software testing?
Leetcode simple question: check whether the numbers in the sentence are increasing
接口测试面试题及参考答案,轻松拿捏面试官
Dlib detects blink times based on video stream
12306: mom, don't worry about me getting the ticket any more (1)
Emqtt distribution cluster and node bridge construction
Brief introduction to libevent
Intensive learning notes: Sutton book Chapter III exercise explanation (ex17~ex29)
Example 071 simulates a vending machine, designs a program of the vending machine, runs the program, prompts the user, enters the options to be selected, and prompts the selected content after the use
In Oracle, start with connect by prior recursive query is used to query multi-level subordinate employees.
遇到程序员不修改bug时怎么办?我教你