Quiz: DP Optimization

A DP recurrence is dp[i] = max(dp[i-1], dp[i-2], ..., dp[i-k]) + cost[i]. What's the time complexity with a monotonic deque?

1. A.O(k) - constant per state
2. B.O(n log k) - using a heap
3. C.O(nk) - same as naive
4. D.O(n) - each index enters and leaves deque once