我在查看一些问题时发现了一个问题(链接),它需要使用动态规划算法。我尝试得出一个递归公式,但我不认为它总是能给出正确的结果。如果我们不考虑限制K,那么很容易有一个递归公式来找到最小时间,我认为也可以使用贪心方法来做到这一点,如果我错了,请纠正我。但是对于限制K,我们需要考虑到在后期可能会想要使用机器A的值i,但它可能已经达到了K的限制。所以这需要回溯。我认为我们可能需要再保留一个维度来解决这个问题。但是我无法想到如何使用额外的维度来包含这种情况。请提供一些帮助。
你有两台机器。有N个工作需要完成。第i个工作在机器A上执行需要Ai的时间,在机器B上执行需要Bi的时间。每项工作都应该在机器A或B上完成。工作应按顺序执行。给定数组A和B和整数K,找到完成工作所需的最短时间,假设您不能连续在同一台机器上完成超过K项工作。这可以在O(NK)的空间和时间内完成。这可以优化为O(NK)的时间和O(N)的空间,并进一步优化为O(NlogN)的时间。