Can this DP be solved in less than O(N * K)

Правка en1, от dcordb, 2018-06-03 04:22:08

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.

Теги dp, optimization

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский dcordb 2018-06-03 04:29:02 359 Tiny change: 'let's say it should be' -> 'let's say answer should be'
en1 Английский dcordb 2018-06-03 04:22:08 482 Initial revision (published)