Readme

2742.Painting-the-Walls

解法1：

此题类似956.Tallest-Billboard，有约束要求两边的高度差为0.所以我们要在dp中加一个维度来标记高度差的状态。

本题我们可以类似地，令dp[i][j]表示完成前i面墙的喷涂需要的最小代价，并且满足其中使用付费工人的时间与使用免费工人的时间之差是j。我们最终的答案是min{dp[n][j]} where j>=0.

我们遍历j的范围时，只需要从-n到n。这是因为如果j<=-n，说明至少使用了n个小时的免费工人，必然已经把任务完成。如果j>=n，说明至少使用了n个小时的付费工人，根据规则我们必然可以搭配n个小时的免费工人，也必然已经把任务完成了。所以dp计算的二维循环的时间复杂度是o(n^2).

注意，本题的转移方程是“从现在到未来的形式”。即已知dp[i][j]，我们考虑第i+1个任务时，根据付费还是免费工人两种方案，给未来的两个状态提供优化：

dp[i+1][j-1] = min(dp[i+1][j-1], dp[i][j]);
dp[i+1][j+time[i+1]] = min(dp[i+1][j+time[i+1]], dp[i][j+OFFSET]+cost[i+1]);

并且我们要注意j+time[i+1]可能会大于n，我们要取cap。这也是我们无法用“从现在到未来的形式”的原因，因为我们无法穷举dp[i][n]=...的来源。

解法2：

此题还有另外一种巧解。我们将每个付费工人强制捆绑若干个免费工人，即看做可以花cost[i]的代价实现time[i]+1的任务。问至少（不是恰好）实现n个任务的最小代价。这是因为“强制捆绑若干个免费工人”的做法无法保证总完成的任务恰好n，极有可能超过n，如果那种情况发生，我们可以再任意踢掉免费的工人（将完成任务的数量降到n）。

此时我们定义状态dp[i][j]表示前i个工人（不一定都用）完成j个任务的最小代价。那么这就是一个典型的背包问题。

同理，我们也得用“从现在到未来的形式”，即已知dp[i][j]，我们考虑第i+1个工人，根据是否雇佣他两种方案，给未来的两个状态提供优化：

dp[i+1][j+time[i+1]+1] = min(dp[i+1][j+time[i+1]+1], dp[i][j]+cost[i+1]); 
dp[i+1][j] = min(dp[i+1][j], dp[i][j]);

同理，我们也要注意j+time[i+1]+1必须cap by n。

最终返回的答案是dp[n][n].