【动态规划】【C++算法】2742. 给墙壁刷油漆

作者推荐

【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字

本文涉及知识点

动态规划汇总

LeetCode2742. 给墙壁刷油漆

给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time ，分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠：

一位需要 付费 的油漆匠，刷第 i 堵墙需要花费 time[i] 单位的时间，开销为 cost[i] 单位的钱。

一位 免费 的油漆匠，刷 任意 一堵墙的时间为 1 单位，开销为 0 。但是必须在付费油漆匠 工作 时，免费油漆匠才会工作。

请你返回刷完 n 堵墙最少开销为多少。

示例 1：

输入：cost = [1,2,3,2], time = [1,2,3,2]

输出：3

解释：下标为 0 和 1 的墙由付费油漆匠来刷，需要 3 单位时间。同时，免费油漆匠刷下标为 2 和 3 的墙，需要 2 单位时间，开销为 0 。总开销为 1 + 2 = 3 。

示例 2：

输入：cost = [2,3,4,2], time = [1,1,1,1]

输出：4

解释：下标为 0 和 3 的墙由付费油漆匠来刷，需要 2 单位时间。同时，免费油漆匠刷下标为 1 和 2 的墙，需要 2 单位时间，开销为 0 。总开销为 2 + 2 = 4 。

提示：

1 <= cost.length <= 500

cost.length == time.length

1 <= cost[i] <= 10⁶

1 <= time[i] <= 500

动态规划

动态规划的状态表示

合法状态：付费工人用时大于等于免费工人用时。

注意：第i项工作，付费工人需要time[i]时间，免费工人需要1。所以前i项工作，付费工人用时和免费工人用时之和不固定。

免费工人用时∈ \in∈[0,500]，付费工人用时大于等于500，必定可行，所以付费用时用时也∈ \in∈[0,500]。

如果直接暴力处理，空间复杂度:O(n²)，处理每份工作时间复杂度O(n)，总时间复杂度O(n³)超时。

状态优化

付费工人用时>=免费工人用时    ⟺    \iff⟺ 付费工人用时 - 免费工人用时 >=0

付费工人用时 - 免费工人用时∈ \in∈[-500,500] 为了方便可以加上500，变成∈ \in∈[0,100don0]

空间复杂度变成：O(n) 总时间复杂度：O(nn)。

动态规划的转移方程

{ d p [ m i n ( 1000 , j + c o s t [ i ] ) ] = m i n ( , p r e [ j ] + c o s t [ i ] ) 使用付费工人 d p [ j − 1 ] = m i n ( , p r e [ j ] ) \begin{cases} dp[min(1000,j+cost[i])] = min(,pre[j]+cost[i]) & 使用付费工人 \\ dp[j-1] = min(,pre[j]) & \\ \end{cases}{dp[min(1000,j+cost[i])]=min(,pre[j]+cost[i])dp[j−1]=min(,pre[j])使用付费工人

动态规划的初始值

dp[500]= 0

动态规划的填表顺序

依次处理各任务。

动态规划返回值

dp[500,1000]的最大值。

代码

核心代码

template<class ELE,class ELE2>
void MinSelf(ELE* seft, const ELE2& other)
{
  *seft = min(*seft,(ELE) other);
}
template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
  *seft = max(*seft, other);
}
class Solution {
public:
  int paintWalls(vector<int>& cost, vector<int>& time) {
    int n = cost.size();
    vector<int> pre(n * 2 + 1, m_iNotMay);
    pre[n] = 0;
    for (int i = 0; i < cost.size(); i++)
    {
      vector<int> dp(n * 2 + 1, m_iNotMay);
      for (int j = 0; j <= n * 2; j++)
      {
        if (pre[j] >= m_iNotMay)
        {
          continue;
        }
        MinSelf(&dp[min(2 * n, j + time[i])], pre[j] + cost[i]);
        MinSelf(&dp[j - 1], pre[j]);
      }
      pre.swap(dp);
    }
    return *std::min_element(pre.begin() + n, pre.end());
  }
  const int m_iNotMay = 1e9;
};

测试用例

template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{ 
  int n;
  vector<int> cost,  time;
  {
    Solution sln;
    cost = { 1, 2, 3, 2 }, time = { 1, 2, 3, 2 };
    auto res = sln.paintWalls(cost, time);
    Assert(res,3);
  }
  {
    Solution sln;
    cost = { 2, 3, 4, 2 }, time = { 1, 1, 1, 1 };
    auto res = sln.paintWalls(cost, time);
    Assert(res, 4);
  }
  
}

2023年6月

class Solution {

public:

int paintWalls(vector& cost, vector& time) {

m_c = cost.size();

vector< int> preTimeAddNumToMinCost(m_c+1,INT_MAX);

preTimeAddNumToMinCost[0] = 0;

for (int ii = 0; ii < m_c; ii++)

{

vector< int> dp = preTimeAddNumToMinCost;

for (int j = 0; j < m_c; j++ )

{

if (INT_MAX == preTimeAddNumToMinCost[j])

{

continue;

}

int iTimeAndNum = j + time[ii] + 1 ;

const int iCurCost = preTimeAddNumToMinCost[j] + cost[ii];

iTimeAndNum = min(iTimeAndNum, m_c);

dp[iTimeAndNum] = min(dp[iTimeAndNum], iCurCost);

}

dp.swap(preTimeAddNumToMinCost);

}

return preTimeAddNumToMinCost[m_c];

}

int m_c;

};