python - 动态编程-洗车

我正在努力解决以下dp问题：
一家洗车公司的员工有一个目标，就是在接下来的D天内洗C辆车由于日程和用品的限制，他一天最多只能洗车。幸运的是，他已经为他提供了一个清单，其中的最大数量的车，他可以每天洗每一天为d天提前，这样[第1天= 2辆车，第2天= 3辆车，第3天= 4辆车）。他能用多少种不同的方法来达到在D天内洗C车的目的，使这些天的总车数等于C。他必须每天至少洗一辆车他不能在几天内完成他的目标，所以必须在几天内完成。
例如，如果他有一个C=5辆车的目标，而且必须在3天内完成，D=3，最大限制为每天可以清洗的{2，3，4}辆车，那么他可以清洗汽车的方式总数将是5这5种方法将是以下组合：
[11 3]
[1 3 1]
[2 2 1]
[2 1 2]
[12 2]
我试过用迭代自下而上的方法来编写伪代码和递归关系，但我不确定如何存储和跟踪每个子问题的全部洗车方法。

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)

最佳答案

这是在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];
}