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有多少种不同的排列组合方法。 |
