求队列物品分配至两同容量集合的O(n³)最低代价算法

现有N个物品排成队列，存在两个容量相同的集合。队列中的每个物品默认需进入前一个物品所在的集合，若切换集合则需花费对应代价cost[i]（cost = [a1, a2, a3, ..., an]）。要求在每个集合的物品数量不超过其容量的约束下，找到总代价最低的物品分配方案。

def solve(i, h, current):
    if i > n:
        return 0

    if h1 == C:
        if current == 1:
            return cost[i - 1]
        else:
            return 0
    elif i - h1 - 1 == C:
        if current == 1:
            return 0
        else:
            return cost[i - 1]
    else:
        if current == 1:
            return min(solve(i + 1, h1 + 1, 1), solve(i + 1, h1, 2) + cost[i - 1])
        else:
            return min(solve(i + 1, h1 + 1, 1) + cost[i - 1], solve(i + 1, h1, 2))

现寻求时间复杂度为O(n³)的算法。

内容的提问来源于stack exchange，提问作者MSQWERTY