Trade Sequence Count
MediumDynamic Programming ยท Optiver
A trader starts with start shares and trades for at most max_days days. Each trading day is one buy or one sell of a single share, and holdings must stay between 0 and cap inclusive after every trade.
Return the number of buy/sell sequences, of any length from 0 to max_days, that leave the trader holding exactly target shares, modulo 1_000_000_007. Sequences of different lengths are different, and the empty sequence counts when start == target.
Example 1
- Input:
- start = 1, target = 1, max_days = 2, cap = 2
- Output:
- 3
- Explanation
- The empty sequence, buy then sell, and sell then buy all end at 1 share without leaving
[0, 2].
Example 2
- Input:
- start = 0, target = 2, max_days = 3, cap = 5
- Output:
- 1
Example 3
- Input:
- start = 0, target = 0, max_days = 4, cap = 1
- Output:
- 3
- Explanation
- Only the empty sequence, buy-sell and buy-sell-buy-sell stay within one share.
Constraints
0 <= max_days <= 10000 <= cap <= 10000 <= start <= cap0 <= target <= cap