【第三轮】8.3-8.9 CareerCup 9.2

9.2 Imagine a robot sitting on the upper left comer of an X by Ygrid. The robot can only move in two directions: right and down. How many possible paths are there for the
robot to go from (0, 0) to (X, Y) ?
FOLLOW UP
Imagine certain spots are "off limits," such that the robot cannot step on them.
Design an algorithm to find a path for the robot from the top left to the bottom right.



回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

【解题思路】DP
【时间复杂度】O(XY)
【空间复杂度】O(XY)
【gist link】
https://gist.github.com/Noahsark/a83c3c51d173164df07c

【解题思路】
f(x,y) = f(x-1, y) + f(x, y-1)
special cases:
f(0,y) = 1;
f(x,0) = 1;
off-limits spots = 0;
【时间复杂度】
O(XY)
【空间复杂度】
O(XY)
【gist link】
https://gist.github.com/f815ad32ccaefe9f6ded

p.s. function of returning path to be implemented...

【解题思路】
paths[row][currCol] = paths[row - 1][currCol] + paths[row][prevCol];


【时间复杂度】
O(x*y)

【空间复杂度】
O(min(x,y))
Follow up: O(x*y)

【gist link】
https://gist.github.com/happyWinner/e3b477593fb3d6c94443

【解题思路】
Totally X+Y Choose X paths
Follow up: Recursion with memorization

【时间复杂度】
O(X*Y)

【空间复杂度】
O(X*Y)

【gist link】
https://gist.github.com/chrislukkk/dd8e7697d5201f773c4c

这道题想请教下各位。答案中的path，add（p）两次是什么意思了？为啥没有成功的情况下，还要再add？谢谢解答。

楼主请问下，这道题的答案看了吗？里面的path，add（p）两次是什么原因了？

【解题思路】
res(x,y) = res(x-1, y) + res(x, y-1); maintain a dp result array and return the last result
【时间复杂度】
O(xy)
【空间复杂度】
O(xy)
【gist link】
https://gist.github.com/movefast/2bf80131abf19db89db1

Test case:
invalid input: null
edge case example: [[0]]

jetfish1900 发表于 2014-9-1 15:54
楼主请问下，这道题的答案看了吗？里面的path，add（p）两次是什么原因了？

啊，看了下CC的这道题答案，发现有点看错题了，我是按leetcode的那道题写的，不过道理是一样的。只是方法不一样，CC答案的方法是recursion，实际也就是dps，但他可没add两次哦，再看一下，没success的时候是remove，因为没success你就要try下一个candidate，所以要把不成功的point remove掉

【解题思路】recursion f(x,y) = f(x-1, y) + f(x, y-1), f(0,y) = 1, f(x,0) = 1, f(0,0)=0
off-limits spots = 0;
【时间复杂度】
O(XY)
【空间复杂度】
O(XY)
【gist link】
https://gist.github.com/bitcpf/3d46b096b96d6838f361