Максимально возможное сбалансированное разделение двоичной подстроки с максимальной стоимостью K

Дан двоичный массив arr[] и массив значений val[] . Задача состоит в том, чтобы найти максимально возможные разбиения двоичного массива, которые можно сделать так, чтобы каждый сегмент содержал равное количество нулей и единиц , используя не более k монет. Каждое разделение стоит (val[i] – val[j]) ² , где i и j — смежные индексы сегмента разделения.

Примеры:

Input: arr[] = {0, 1, 0, 0, 1, 1}, val[] = {2, 5, 1, 3, 6, 10}, k = 20
Output: 1
Explanation: Splits can be done in the following way: 0 1 | 0 0 1 1 and cost = (5 –  1)² = 16 ≤ 20.

Input: arr[] = {1, 0, 0, 1, 0, 1, 1, 0}, val[] = {9, 7, 5, 2, 4, 12, 3, 1], k = 10
Output: 2
Explanation: Splits can be done in the following way: 1 0 | 0 1 | 0 1 1 0

Подход: Задача может быть решена с помощью динамического программирования (подход «сверху вниз»).
Выполните следующие шаги:

1. Инициализируйте матрицу 2d, скажем, dp размеров K * N.
2. Для каждого индекса есть два варианта: делать разрез по этому индексу или не делать разрез по этому индексу при условии, что количество нулей и единиц равно.
3. Запомните значения, чтобы использовать их снова
4. Максимально увеличьте значение count_splits , чтобы получить результирующие максимальные сокращения.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность : O(N*K)
Вспомогательное пространство : O(N*K)