Задача поиска подмножеств с минимальной суммой Amazon

Есть список задач - массив чисел. Каждое число представляет собой сложность задачи. Задачи идут в строгом порядке, который нельзя менять. Так же дано количество дней. Сложность дня определяется самой сложной задачей, решенной в этот день. 
Нужно написать функцию, которая разобьет задачи по дням так, чтобы общая сложность (сумма) было минимальная. 


Пример 1:

Задачи [3, 1, 4, 2, 5]
2 дня.

Решение:

первый день [3] -> 3, 

второй день [1, 4, 2, 5] -> 5 (т.к. Сложность дня определяется самой сложной задачей)
3 +5 = 8


Пример 2:

Задачи [2, 4, 7, 3, 5, 1, 6]
3 дня.

Решение:

первый день [2] -> 2,

второй день [4] -> 4
Третий день [73516] -> 7
2+ 4 + 7 = 13

Ищу идеи для решения сложностью меньше O(n^m)

0

Сообщение от vantfiles Хорошая аналогия. Вот только у нас есть 3 ямки и 10 мячиков.

Ямки - границы между задачами. Мячики - границы между днями. Мы некоторые границы между задачами помечаем (с помощью мячиков) как границы между днями. Поэтому 10 задач и 9 ямок, 3 дня и 2 мячика. И количество способов это сделать (математики говорят - сочетания).

Добавлено через 4 минуты
Чтобы разбить 5 задач на 3 дня я должен два пробела из четырех заменить на черточки. Например, так:

0

Сообщение от vantfiles Объясните, пожалуйста, в какую формулу и что именно Вы подставляете. Откуда при "4 задачи, 3 дня." в формуле появляется двойка?

Представьте ленту, на которой в ряд написаны 4 числа - это наши задачи. Нам нужно разрезать эту ленту на 3 части - на три дня.

Мы можем разрезать ленту только между задачами/числами - между первым и вторым числом, между вторым и третьим и т.д. Количество возможных мест для разреза на один меньше, чем количество задач. Задач 4, а количество возможных мест для разреза - три (4-1 = 3).

Чтобы разрезать ленту на три части нам нужно сделать 2 разреза - на один меньше, чем количество дней. Дней 3, но количество разрезов, которые будем делать - два (3-1 = 2).

Есть формула, которая определяет, сколько существует разных вариантов выбрать k элементов из n возможных - n! / (k! * (n-k)!).
Обозначается как C(n;k)

В данном случае - варианты выбрать 2 разреза из 3 возможных. Количество вариантов их равно 3! / (2! * (3-2)!)

Аналогично с 10 задачами и тремя днями. Возможных разрезов 9 (т.е. 10-1), надо выбрать из них 2 (3-1). Количество вариантов 9! / (2! * (9-2)!)

Итого, если мы имеем N задач и K дней, то количество вариантов равно C(n-1; k-1)

1