1269. Number of Ways to Stay in the Same Place After Some Steps¶
题目信息¶
- 题号:
1269
- 难度:
Hard
- 主题:
动态规划、位置状态、计数
- 原题:
- 重点:
从下标
0出发,每步可左移、右移或停留,但不能越界;统计恰好执行steps步后回到下标0的方案数
题目重述¶
有一个长度为 arrLen 的数组,当前位置初始为下标 0。每一步可以向左移动一格、向右移动一格,或者停留在原地,但移动后必须仍位于合法下标范围内。
请统计恰好执行 steps 步后回到下标 0 的不同操作序列数量,并返回结果对 10^9 + 7 取模后的值。
1 <= steps <= 500,1 <= arrLen <= 10^6。
自建示例¶
多次离开原点后仍可返回:
输入:steps = 4, arrLen = 3
输出:9
解释:统计所有由左移、右移和停留组成且不越界、四步后回到下标 0 的序列,共有九种。
数组只有一个位置时每一步都只能停留:
输入:steps = 5, arrLen = 1
输出:1
解释:唯一合法操作序列是连续停留五次。