我无法在 leetcode 中记住这个问题？我做错了什么？

发布于 2025-01-19 01:34:44 字数 724 浏览 3 评论 0 原文

问题链接： https://leetcode.com/problems/nique-paths/nique-paths/

与回忆但需要相同的时间： httpps://leetcode.com/leetcode.com/submissions/submissions/detail/detail/detail/detail/672801459/

没有回忆的代码：

带有回忆的代码，但需要相同的时间：

我已经编写了记忆的代码，但是有些行动，请告诉我我在做什么错。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

森末i 2025-01-26 01:34:44

记忆不是问题，

我只是认为即使实现按照您预期的方式工作，它仍然太慢，您可能有多达 10 亿条路径需要探索，每条路径可能需要 100 多个步骤。

用组合学尝试

另一种方法是从组合学的角度看问题：
注意每条路径如何由向下或向右移动的列表表示
所以路径总数就是排列向下和向上移动的方式数

从原来的问题中，我们可以看到有 m-1 向下移动和 n-1< /code> 向上移动。在组合学中，我们说结果是(m-1) + (n-1)中m-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))

Memoization is not the problem

I just think that even if the implementation works the way you intend it, it is still too slow, you could have up to one billion path to explore wich could each take more than 100 steps.

Try it with combinatorics

Another approach is to look at the problem from a combinatorics side:
notice how each path could be represented by a list of down or right moves
so the total number of paths is just the number of ways to arrange the down and up moves

From the original question, we can see that there are m-1 moves down and n-1moves up.
In combinatorics, we say that the result is the combination of m-1 in (m-1) + (n-1)

Here is some code that would do that:

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))

回复收藏 0 原文

~没有更多了~

关于作者

放血

暂无简介

文章

27 人气

关注发私信

友情链接

文江博客

我无法在 leetcode 中记住这个问题？我做错了什么？

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论