Loading... > https://leetcode.cn/problems/painting-the-walls/description/?envType=daily-question&envId=2024-05-02 免费的油漆匠每单位时间可以刷好一面墙，但只有在付费油漆匠工作时才会工作，所以付费油漆匠的工作时间应该大于等于 $n / 2$ 。 已知：付费油漆匠刷墙数量 + 免费油漆匠刷墙数量 = $n$ ，且 付费油漆匠刷墙的时间之和 $\geq$ 免费油漆匠刷墙数量，因此可以得到 $\sum$ (付费油漆匠刷墙时间 + 1) $\geq n$ 。 将 $time[i] + 1$ 看成物品体积，$cost[i]$ 看成物品价值，题目就可以转化为：从 $n$ 个物品中选择体积和至少为 $n$ 的物品，最小的价值和为多少？ 为 01 背包的变体，因此用 DP 求解。 ```c++ class Solution { public: int paintWalls(std::vector<int>& cost, std::vector<int>& time) { const int n = cost.size(); std::vector<int> dp(n + 1, INT_MAX / 2); dp[0] = 0; for (int i = 0; i < n; i++) { for (int j = n; j > 0; j--) { dp[j] = std::min(dp[j], dp[std::max(j - time[i] - 1, 0)] + cost[i]); } } return dp[n]; } }; ``` - 时间复杂度：$O(n^2)$ ，其中 $n$ 为墙的个数。题目中状态有 $O(n^2)$ 中，每个状态的计算时间为 $O(1)$ ，因此时间复杂度为 $O(n^2)$ 。 - 空间复杂度：$O(n)$ 。 最后修改：2024 年 06 月 29 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏