我在查看一些问题时发现了一个问题（链接），它需要使用动态规划算法。我尝试得出一个递归公式，但我不认为它总是能给出正确的结果。如果我们不考虑限制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）的时间。