动态规划洗车

Question

我正在努力解决以下DP问题：

一家洗车公司的员工有一个目标，就是在接下来的D天里洗C辆车。由于日程和用品的限制，他每天最多只能洗车。幸运的是，他已经提前D天向他提供了每天可洗车的最大数量清单，以便[第1天=2辆车，第2天=3辆车，第3天=4辆车）。他能用多少种不同的方法来达到在D天内洗C辆车的目标，使这几天的车总数等于C。他每天至少要洗1辆车。他不能在几天内完成他的目标，所以必须在几天内完成。你知道吗

例如，如果他的目标是C=5辆车，并且必须在3天内完成D=3，每天最多只能洗{2，3，4}辆车，那么他可以洗的方式总数将是5种。这5种方式可以是以下组合：

[1 1 3]
[1 3 1]
[2 1]
[2 1 2]
[12]

我试着用自底向上的迭代方法来编写伪代码和递归关系，但我不确定如何存储和跟踪每个子问题的洗车方法

def findWays(T, D, limits):

    M = [[0]*(T+1) for i in range(D+1)]

    for i in range(1, D+1):
        dayLimit = limits[i-1]
        for j in range(1, T+1):
            if i == 1:
                if j <= dayLimit:
                    M[i][j] = 1
            else:
                for k in range(1, j):
                    if (j - k) > dayLimit:
                        continue
                    if (dayLimit - M[i-1][k]) >= 1:
                            M[i][j] = M[i][j] + M[i-1][k]
    print(M)

Answer 1

这里是在O(D*C*C)时间内工作的动态规划解决方案

D=3，C到10的样本矩阵，限值为[2，3，4]。你知道吗

int NumberOfWays(int c, int d, int[] limits)
{
    // let's t[i, j] be amount of ways j cars can be washed in i days

    var t = new int[d + 1, c + 1];

    for (int day = 1; day <= d; day++)
    {
        int dayLimit = limits[day - 1];

        for (int cars = day; cars <= c; cars++)
        {
            if (day == 1) // first day
            {
                if (cars <= dayLimit)
                    t[day, cars] = 1;
            } else // not first day
            {
                // okay, number of ways given amount of cars can be washed
                // on certain day can be calculated using amounts possible on the previous day

                for (int carsOnPrevDay = 1; carsOnPrevDay < cars; carsOnPrevDay++)
                {
                    if (cars - carsOnPrevDay > dayLimit)
                        continue; // day limit exceeded

                    t[day, cars] += t[day - 1, carsOnPrevDay];
                }
            }
        }
    }

    return t[d, c];
}

Answer 2

注意：这个问题和另一个常见的问题是一样的：有多少种方法可以使用d1，d2，d3，…，dn边的骰子来滚动给定的总数。你知道吗

如果在i天内有C[n，i]种洗车方式，则在i+1天内有sum（C[n-k]，i+1），k=1..D[i+1]）种洗车方式。边条件为：C[0，0]=1，C[0，0]=0。你知道吗

这就直接给出了使用O（C）空间的O（Cmax（D）| D |）算法。你知道吗

def cars(C, D):
    r = [1] + [0] * C
    for d in D:
        for i in range(C, -1, -1):
            r[i] = sum(r[j] for j in range(max(0, i-d), i))
    return r[C]

print(cars(5, [2, 3, 4]))

您可以做得更好一点，因为内部循环执行的是d值的滚动求和，平均每个C元素的计算时间为O（1）。你知道吗

def cars(C, D):
    r = [1] + [0] * C
    for d in D:
        S = 0
        for i in range(C, -d-1, -1):
            if i >= 0:
                S += r[i]
            if i + d <= C:
                S -= r[i+d]
                r[i+d] = S
    return r[C]

print(cars(5, [2, 3, 4]))

因为在不损失一般性的情况下，max（D）<；C，这是O（C | D |），仍然使用O（C）空间。你知道吗

如果有帮助的话，这段代码实际上是在计算多项式p[D[0]]*p[D[1]]*.的第一个C+1项。。。*P[D[len（D）-1]]，其中P[D]=x+x^2+。。。+x^d。结果中x^C的系数就是问题的答案。你知道吗

Answer 3

更具教育意义的是，我尝试手动运行您的算法（忽略边界问题），得到以下矩阵：

但您可能更希望看到这个（注意，由于懒惰，我忽略了填充无效值）：

考虑一下调整一下你的总和，特别是在第一天，因为某些原因不可能洗2或3辆车。之后，返回OPT[D, C]是正确的。你知道吗