#1269

Number of Ways to Stay in the Same Place After Some Steps

candidate master · 1425 · lc hard +32 · verified · 50% accepted · 1,598 likes · top 38%

⚑ Linear 1D DP

Description

A pointer starts at index 0 in an array of size arrLen. At each step, the pointer can move one position left, one position right, or stay in place — but must never go outside the array.

Given steps and arrLen, count the number of distinct ways the pointer can return to index 0 after exactly steps steps. Since the answer can be very large, return it modulo 109 + 7.

Example 1:

Input: steps = 3, arrLen = 2
Output: 4
Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay

Example 2:

Input: steps = 2, arrLen = 4
Output: 2
Explanation: There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, Stay

Example 3:

Input: steps = 4, arrLen = 2
Output: 8

Code

1
2
3