A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?
Example 1:
1 | Input: m = 3, n = 7 |
Example 2:
1 | Input: m = 3, n = 2 |
Example 3:
1 | Input: m = 7, n = 3 |
step down:3, step right: 7
ddrrrrrr: move 2d6r
rrrrrrdd: move 2d6r
…
all move 8, select 2 down
C8,2= 8!/2!(8-2)! =8765432/265432=87/2=28
1 | # TC: O(1), SC: O(1) |
DP
1 | # TC: O(mn), SC: O(n) |
如果你覺得這篇文章很棒,請你不吝點讚 (゚∀゚)