Эффективный поход – динамическое программирование ⇐ JAVA

[Anonymous]

Сегодня я получил следующий вопрос, но решил его неоптимально. Я хотел получить некоторую помощь, как найти наиболее оптимальное решение:
Вопрос в следующем; Путешественнику необходимо пройти небольшое количество маршрутов в рекордные дни. Ему нужно делать хотя бы один след в день, но в противном случае он может сделать столько, сколько возможно. Он хочет минимизировать сумму самых длинных маршрутов за каждый день. Например, [10, 9, 2, 15, 11] и Records =2 дают оптимальное значение 25
Мое решение включало простое рекурсивное решение - для каждого день записи, выполняем итерацию слева направо, отслеживая максимум, а затем рекурсивно вызывая функцию, чтобы получить результат для записи -1, а затем отслеживая минимум:

Код: Выделить всё

 public static int minTrails(List trails, int currDay, int days) {
// Count all remaining trails
if (days == 1) {
return trails.subList(currDay, trails.size()).stream().mapToInt(x -> x).max().orElse(0);
}

int totalDays = trails.size();
// Recursive case: Try different splits of the trails
int maxLength = 0;
int currMin = Integer.MAX_VALUE;

// Try to take at least one trail, up to n - days trails for the current day
for (int i = currDay; i 

Подробнее здесь: [url]https://stackoverflow.com/questions/79037045/effective-hiking-dynamic-programming[/url]