hardDynamic Programming 1DAI-applied~40 min
Ways an Agent Returns to Start After K Steps
An agent on a 1-D track of fixed length starts at index 0 and, each step, moves left, moves right, or stays. Count the distinct step sequences that return it to index 0 after exactly k steps without leaving the track.
Problem
You start at index 0 of an array of length arrLen. In each of steps moves you may go left, right, or stay, never leaving the array bounds. Return the number of ways to be back at index 0 after exactly steps moves, modulo 1e9+7.
Input
Integers steps and arrLen.
Output
An integer: the count of returning sequences modulo 1e9+7.
Constraints
- 1 <= steps <= 500
- 1 <= arrLen <= 10^6
- Counts are taken modulo 1e9+7.
Examples
Example 1
Input
steps = 3, arrLen = 2
Output
4
Four step sequences return to index 0.
Example 2
Input
steps = 2, arrLen = 4
Output
2
Either stay-stay or right-left.