有效徒步——动态规划

Question

我今天遇到了以下问题，并没有得到最佳解决。我想获得一些帮助，如何获得最佳解决方案：

问题是；徒步旅行者需要在

record

天完成一系列步道。它每天至少需要进行一次测试，但除此之外他可以做尽可能多的测试。他希望最小化每天最长路径的总和。例如

[10, 9, 2, 15, 11]

和记录 =2 产生最优的

25

我的解决方案涉及一个简单的递归解决方案 - 对于每个记录日，从左到右迭代，跟踪最大值，然后递归调用该函数以获取

record -1

的结果，然后跟踪最小值：

 public static int minTrails(List<Integer> 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 <= totalDays - days; i++) {
            maxLength = Math.max(maxLength, trails.get(i));

            // Recursively solve for the remaining trails and days
            int maxOfRest = minTrails(trails, i + 1, days - 1);

            // The current result is the maximum sum of the current day and the rest of the days
            currMin = Math.min(maxLength + maxOfRest, currMin);
        }

        return currMin;
    }

这让人尖叫某种形式的DP。稍后我意识到的一件事是预先计算从

trail=i

开始直到数组末尾的所有最大值。这实际上是从

i

如果

record=1

开始的每个子阵列的所有解决方案，即只剩下一天时间来完成所有剩余的追踪。我们可以从右向左迭代，并跟踪最大值，将结果存储在数组中，产生

O(n)

。然后，如果我们需要计算

record=2

，我们可以以同样的方式迭代，从i=0开始，每次走一条轨迹，在每个i处，从memoization中询问record=1的结果，即

O(n) 

。因此，对于 record=2，我现在有了

O(n)

解决方案。

这导致了我更通用的方法。对于record=3，我需要预先计算record=2，对于每个i，最优子解。这意味着计算上面的每个

i

解决方案（从 i 迭代到结束，在我进行过程中重复使用 record=1）。但现在每个起点都完成了

i

，这意味着每个记录日的时间复杂度为

O(n^2)

。

这意味着

record=1

的计算是

O(n)

，最终解决方案是

O(n)

并且任何中间记录天数记忆需要

O(n^2)

，产生

O(record * n^2)

解决方案。

我想问是否：

1. 我修改后的方法真的有意义吗？
2. 似乎应该有一种方法让record=2使用一些从右到左的迭代来实现O(n)计算。
3. 我是否把这个问题归入了错误的范畴？也许有一种贪婪的方法吗？

Answer 1

有人能想到贪婪方法的反例吗？我们按照数量级的降序排列每个元素，并从它开始尽可能向左和向右扫描，同时留下足够的天数，因为有需要的部分，以构建下一个子数组一天的足迹？ （我们通过贪婪地选择哪一边包含更大的元素来解决更左或更右的选择。）

在示例中，我们从 15 开始，然后选择 11 延伸到的一侧，将 10 保留为另一天所需的最小尺寸部分。

10, 9, 2, 15, 11
    <———————-——>