Unique Paths

找到不重复的能到达目标的路径数

 

my solution (8ms)

典型的可以用递归解决的问题

结果超时了, 想了一下:

这样子的话, 大多数的迭代都会重复

所以更改了一下代码:

通过保存的形式来去掉一些可以重用的计算, 虽然过了, 但是效果不理想

emm... 我没有再从树中能总结出什么好的规律...

 

the best solution

简洁又高效, 真是个漂亮的小东西

思路是这样的:

上述分别是 3, 2 和 3, 3 的情况, 假设 rebot 在左下角, star 在右上角(本质上不会有什么改变, 只是换了方向)

从 star 开始往后退, 每一个节点的次数都是他的 上节点次数 + 右节点次数 直到循环结束

最后的左下角就是 rebot 的次数

这样的算法复杂度是 O(n)