CODEWITHSUNDEEP
arraysalgorithmdynamic-programmingminimization
iheartcoding124
iheartcoding124

Reputation: 23

What is an efficient dynamic programming algorithm to minimize the total cost of an array w/o removing two adjacent elements?

I am trying to design an efficient, dynamic programming algorithm that, given an array of integers of length n and a limit of the number of integers that can be removed k, will minimize the total cost (i.e. the sum of integers) of the array by removing elements from it such that no two, consecutive elements in the array are removed. I think this is basically the same as maximizing the cost of the total amount of integers I have removed, but I am not completely sure. Quite frankly, I am completely stuck on the recurrence step of the algorithm.

Edit: The number of elements that are removed can be less than or equal to the input of k.

Upvotes: 0

Views: 485

Answers (1)

MBo
MBo

Reputation: 80187

Yes, you are right, maximization of removed elements sum is equal to minimization of the rest. But solution is essentially the same.

Recurrence:

MaxDel(i, m) = Max(A[i] + MaxDel(i+2, m+1), MaxDel(i+1, m)) if (m < k and i < N) else 0

Description: We can remove i-th element, in this case we must omit i+1 and go to i+2, or we can omit i-th and go to the next. Stop when we have k removed elements or index goes out of array.

Upvotes: 2

Related Questions