标签: 动态规划
难度: Hard
有一个长度为 arrLen 的数组，开始有一个指针在索引 0 处。
每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。
给你两个整数 steps 和 arrLen ，请你计算并返回：在恰好执行 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
提示：
1 <= steps <= 5001 <= arrLen <= 106运行时间: 50 ms
内存: 16.0 MB
class Solution:
def numWays(self, steps: int, arrLen: int) -> int:
arrLen=min(steps//2+2,arrLen)
if arrLen==1:
return 1
dp=[0]*(arrLen+2)
dp_new=[0]*(arrLen+2)
dp_new[2]=1
dp_new[1]=1
# print(dp_new)
for i in range((steps-1)//2):
dp,dp_new=dp_new,dp
for j in range(1,arrLen+1):
dp_new[j]=(dp[j-1]+dp[j]+dp[j+1])%1000000007
# print(dp_new)
else:
if steps%2:
ans=0
for j in range(1,arrLen+1):
ans+=dp_new[j]*dp[j]
else:
ans=0
for j in range(1,arrLen+1):
ans+=dp_new[j]*dp_new[j]
return ans%1000000007
题解采用了动态规划的方法。定义一个 dp 数组，其中 dp[j] 表示在当前步数下，指针位于位置 j 的方案数。由于指针每一步可以向左、向右移动或停在原地，因此状态转移方程为 dp_new[j] = (dp[j-1] + dp[j] + dp[j+1]) % 1000000007。此外，由于指针不能超出数组长度或数组起始位置，数组长度可以通过 min(steps//2+2, arrLen) 进行优化，这是因为指针最远只能走到最远的距离，再走回来，而这个距离大约是 steps 的一半。最后，根据步数的奇偶性，计算最终停在原点的方案数。
时间复杂度: O(steps * min(steps/2+1, arrLen))
空间复杂度: O(min(steps/2+2, arrLen))
class Solution:
def numWays(self, steps: int, arrLen: int) -> int:
arrLen = min(steps//2 + 2, arrLen) # 优化数组长度
if arrLen == 1:
return 1 # 只有一个位置时，唯一方案就是不动
dp = [0] * (arrLen + 2)
dp_new = [0] * (arrLen + 2)
dp_new[2] = 1
dp_new[1] = 1 # 初始化起始位置的方案
# 进行动态规划更新
for i in range((steps - 1) // 2):
dp, dp_new = dp_new, dp # 交换数组，准备下一轮计算
for j in range(1, arrLen + 1):
dp_new[j] = (dp[j - 1] + dp[j] + dp[j + 1]) % 1000000007 # 更新状态
if steps % 2:
ans = 0
for j in range(1, arrLen + 1):
ans += dp_new[j] * dp[j] # 奇数步，计算最终方案数
else:
ans = 0
for j in range(1, arrLen + 1):
ans += dp_new[j] * dp_new[j] # 偶数步，计算最终方案数
return ans % 1000000007 # 返回结果
动态规划是解决这类问题（计数问题和存在多个状态转移的问题）的一种有效方法。在这个问题中，每一步的状态（指针位置）取决于前一步的状态，形成了状态转移关系，这是动态规划的典型应用场景。使用动态规划可以有效地利用之前计算的结果，避免重复计算，提高算法效率。
这个优化策略基于指针从起始位置出发最远能到达的距离的考虑。理论上指针最远可以移动到`steps//2`的位置，然后再返回。+2是为了考虑边界情况，例如在计数过程中需要考虑指针可能停留在起始点或者稍微超过最远点的情况。这种优化可以减少内存使用并加速计算过程，因为不需要在数组中保留不可能到达的位置。
在这个特定的问题中，每一步，指针只能从当前位置不动或者移动到相邻的左边或右边的位置。因此，对于任何位置`j`，下一步的状态只能由`dp[j-1]`（左边的位置），`dp[j]`（当前位置），和`dp[j+1]`（右边的位置）这三个状态决定。这是根据问题的规则设定的，即每步只能移动至最近的相邻位置或停留在原地。
交换`dp`和`dp_new`数组的目的是为了在每一轮迭代中重用数组，避免额外的数组创建和数据复制开销。这种技术称为数组滚动，可以将空间复杂度从O(n * m)降低到O(n)，其中n是状态数组的大小，m是步数。通过交换指针指向，可以实现在更新当前状态的同时保留前一状态的信息，从而有效地进行动态规划的状态转移。