d****n 发帖数: 397 | 1 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?
这个用递归judge small可以通过,但是judge large给出timelimit exceeded at (23,
12),有没有比递归更好的方法? |
l********t 发帖数: 878 | |
c********p 发帖数: 1969 | |
d****n 发帖数: 397 | 4 好吧,感觉这个就是递归的反向操作,没有想到差别会很大。
【在 l********t 的大作中提到】 : bottom-up : http://tech-lightnight.blogspot.com/2013/01/unique-paths.html
|
r*********n 发帖数: 4553 | 5 因为这个是dynamic programming
你还可以用counting的方法:
一共有m+n-2步,从中选m-1步往下,剩下的就往右,所以一共有
m+n-2 choose m-1这么多种走法
【在 d****n 的大作中提到】 : 好吧,感觉这个就是递归的反向操作,没有想到差别会很大。
|
g**G 发帖数: 767 | 6 or use a hashmap to memorize the intermediate results |
e****d 发帖数: 333 | 7
【在 d****n 的大作中提到】 : 好吧,感觉这个就是递归的反向操作,没有想到差别会很大。
|
i****y 发帖数: 84 | |
s***e 发帖数: 403 | 9 我觉得这更像是一个排列组合的题目。
向右定义为1,向下定义为0
现在就是这些10有多少种不同的排列组合方法。 |