I've got a following problem to solve:
You are given a list of positive integers [x_1;x_2;...;x_n]. You are allowed to
change 2 integers standing next to each other to one equal to their sum. (So for
example in list [x_1;...;x_3;x_4;x_5;x_6;...;x_n] you pick x_4 and x_5 and the new list
becomes [x_1;...;x_3;(x_4+x_5);x_6;...;x_n]). Find the minimum number of such changes
needed to get a list in which integers are in strictly increasing order.
How to approach such a problem? Intuitively it looks like Dynamic Programming problem (something like multiplying matrices) but I cannot find any connected subproblems. Any idea how to solve this using something else than brute-force?
Aucun commentaire:
Enregistrer un commentaire