我不能用leetcode回忆录这个问题？我做错什么了？
我不能用leetcode回忆录这个问题？我做错什么了？
提问于 2022-04-03 07:10:25
问题链接：https://leetcode.com/problems/unique-paths/
用回忆录编写代码，但花费同样的时间:https://leetcode.com/submissions/detail/672801459/
没有回忆录的代码：https://leetcode.com/submissions/detail/672800593/
用回忆录编写代码，但花费同样的时间:https://leetcode.com/submissions/detail/672801459/
我写了回忆录的代码，但有些东西不起作用，请告诉我我做错了什么。
回答 1
Stack Overflow用户
发布于 2022-04-03 07:43:21
追忆不是问题
我只是认为，即使实现按照您的意愿工作，它仍然太慢，您可以有多达10亿的路径来探索
用组合数学试试看
另一种方法是从组合学的角度来看待这个问题:注意每条路径是如何用向下或向右移动的列表来表示的，所以路径的总数就是排列上下移动的方法的数量。
从最初的问题中，我们可以看到m-1向下移动，n-1向上移动。在组合学中，我们说结果是the combination of m-1 in (m-1) + (n-1)。
下面是一些代码可以做到这一点：
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
def factorial(a):
out = 1
for i in range(1, a+1):
out *= i
return out
def combination(a, b):
out = 1
for i in range(b-a+1, b+1):
out *= i
return out // factorial(a)
return combination(m-1, (m-1)+(n-1))页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/71723747
复制相关文章
相似问题
腾讯云开发者
