leetcode-1269 停在原地的方案数

leetcode-1269 停在原地的方案数

题目

有一个长度为 arrLen 的数组,开始有一个指针在索引 0 处。
每一步操作中,你可以将指针向左或向右移动 1 步,或者停在原地(指针不能被移动到数组范围外)。
给你两个整数 steps 和 arrLen ,请你计算并返回:在恰好执行 steps 次操作以后,指针仍然指向索引 0 处的方案数。
由于答案可能会很大,请返回方案数 模 10^9 + 7 后的结果。

解题思路

  1. 暴力回溯 会超时
  2. 动态规划
    dp[i][j]表示第i步到第j位置的方案数
    在第i个位置,共有三种走法
    即dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j+1]
    初始化 dp[0][0]=1
    在i=0或者i=arrLen的位置,只有两种走法
    因为最后的终点是0,所以j位置最远走到steps/2

代码

class Solution:
    def __init__(self):
        self.res=0
    def numWays(self, steps: int, arrLen: int) -> int:
        index=0
        cur_step=0
        self.move(steps,arrLen,index,cur_step+1)
        self.move(steps,arrLen,index+1,cur_step+1)
        return self.res
    def move(self,steps,arrLen,index,cur_step):
        if cur_step<=steps:
            if index==0 and steps==cur_step:
                self.res+=1
            if index!=0:
                self.move(steps,arrLen,index-1,cur_step+1)
            self.move(steps,arrLen,index,cur_step+1)
            if index!=arrLen-1:
                self.move(steps,arrLen,index+1,cur_step+1)
class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        mod=10**9 + 7
        max_len=min(steps//2,arrLen-1)
        dp=[[0]*(max_len+1) for i in range(steps+1)]
        dp[0][0]=1
        for i in range(1,steps+1):
            for j in range(0,max_len+1):
                dp[i][j]=dp[i-1][j]
                if j>0:
                    dp[i][j]+=dp[i-1][j-1]
                if j<max_len:
                    dp[i][j]+=dp[i-1][j+1]
                dp[i][j]=dp[i][j]%mod
        return dp[steps][0]
上一篇:input 标签的监听事件总结


下一篇:python 爬虫 汽车之家车辆参数反爬