Leetcode 1269:停在原地的方案数(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1269:停在原地的方案数(超详细的解法!!!)

in leetcode with 0 comment

有一个长度为 arrLen 的数组,开始有一个指针在索引 0 处。

每一步操作中,你可以将指针向左或向右移动 1 步,或者停在原地(指针不能被移动到数组范围外)。

给你两个整数 stepsarrLen ,请你计算并返回:在恰好执行 steps 次操作以后,指针仍然指向索引 0 处的方案数。

由于答案可能会很大,请返回方案数 10^9 + 7 后的结果。

示例 1:

输入:steps = 3, arrLen = 2
输出:4
解释:3 步后,总共有 4 种不同的方法可以停在索引 0 处。
向右,向左,不动
不动,向右,向左
向右,不动,向左
不动,不动,不动

示例 2:

输入:steps = 2, arrLen = 4
输出:2
解释:2 步后,总共有 2 种不同的方法可以停在索引 0 处。
向右,向左
不动,不动

示例 3:

输入:steps = 4, arrLen = 2
输出:8

提示:

解题思路

这个问题非常简单,我们定义$f(i,j)$表示总的方案个数,其中$i$表示当前的步数,$j$表示当前的位置。那么:

from functools import lru_cache
class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        mod = 10**9 + 7
        @lru_cache(None)
        def dfs(s, l):
            if s == steps:
                if l == 0:
                    return 1
                return 0
            
            return (dfs(s + 1, l) + (dfs(s + 1, l + 1) if l < arrLen-1 else 0 )+ (dfs(s + 1, l - 1) if l else 0)) % mod
        return dfs(0, 0)

同样,我们也可以通过动态规划解该问题

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        m, n, mod = steps, min(steps, arrLen), 10**9 + 7
        dp = [[0]*(n + 1) for _ in range(m + 1)]
        dp[0][0] = 1
        
        for i in range(1, m + 1):
            for j in range(n):
                dp[i][j] = (dp[i-1][j] + (dp[i-1][j-1] if j else 0) + dp[i-1][j+1]) % mod
        return dp[m][0]

可以使用滚动数组优化上面的写法。

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        m, n, mod = steps, min(steps, arrLen), 10**9 + 7
        dp = [0]*(n + 1)
        dp[0] = 1
        
        for i in range(1, m + 1):
            dp2 = [0] * (n + 1)
            for j in range(n):
                dp2[j] = (dp[j] + (dp[j-1] if j else 0) + dp[j+1]) % mod
            dp = dp2
        return dp[0]

一个pythonic的写法

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        A, mod = [0, 1], 10**9 + 7
        for t in range(steps):
            A[1:] = [sum(A[i - 1:i + 2]) % mod for i in range(1, min(arrLen + 1, t + 3))]
        return A[1] % mod

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses