Given an array with N elements you need to choose exactly K non-consecutive elements from it such that the sum of the elements will be minimum.
Constraints:
- 1 ≤ N ≤ 105
- 1 ≤ K ≤ N
- - 109 ≤ ai ≤ 109
I know how to solve this in O(N·K) by using DP(i, m) = minimum sum that can be obtained in prefix i taking exactly m elements.
Can it be done faster than that? Thanks beforehand.
