LeetCode 🔴 2742. Painting the Walls

🔗 🔴 2742. Painting the Walls 2425

tags: Weekly Contest 350 動態規劃(DP) 陣列(Array)

題意

給定兩個長度為 $n$ 的整數陣列 $\text{cost}$ 和 $\text{time}$，分別表示繪製 $n$ 面不同牆壁的成本和所需時間。

現在有兩位油漆工可供選擇：

• 一位付費油漆工，用 $\text{time}[i]$ 單位時間繪製第 $i$ 面牆壁，花費 $\text{cost}[i]$ 單位金錢。
• 一位免費油漆工，以 $1$ 單位時間繪製任何牆壁，費用為 $0$。但只能在付費油漆工已經在工作時，才能使用。

請返回繪製 $n$ 面牆壁所需的最少金額。

約束條件

• $1 \leq \text{cost.length} \leq 500$
• $\text{cost.length} == \text{time.length}$
• $1 \leq \text{cost}[i] \leq 10^6$
• $1 \leq \text{time}[i] \leq 500$

思路

方法一：狀態優化的動態規劃

令 $dfs(i, j, k)$ 表示考慮前 $i$ 面牆壁，且付費油漆工耗時 $j$ 單位時間，免費油漆工耗時 $k$ 單位時間的最小花費。則對於第 $i$ 面牆壁，有讓付費油漆工繪製和讓免費油漆工繪製兩種選擇。故可以寫出以下遞迴式：

• $dfs(i, j, k) = min(dfs(i-1, j, k + 1), dfs(i-1, j+time[i-1], k) + cost[i-1])$
  • 若第 $i$ 面牆壁由免費油漆工繪製，則 $j$ 不變，$k$ 加 $1$ 後遞迴；
  • 若第 $i$ 面牆壁由付費油漆工繪製，則 $j$ 加上 $time[i-1]$，$k$ 不變後遞迴，並將遞迴結果加上 $cost[i-1]$。
  • 兩者取最小值即可。
• 終止條件：$dfs(0, j, k) = 0$ if $j \geq k$ else $\infty$
  • 終止時需要付費時間超過免費的時間，否則不合法，返回 $\infty$。
• 遞迴入口：$dfs(n, 0, 0)$
• 剪枝：$j - k \geq i$ 時，表示免費油漆工可以繪製完剩餘的所有牆壁，返回 $0$ 。

但上述遞迴式的狀態數量過多，會 MLE ，因此需要進行 狀態優化 。可以發現，我們只關注 $j$ 和 $k$ 的差值，因此可以重新定義遞迴式，令 $dfs(i, j)$ 表示考慮前 $i$ 面牆壁，且付費油漆工耗時減去免費油漆工耗時為 $j$ 單位時間的最小花費。則遞迴式為：

• $dfs(i, j) = min(dfs(i-1, j-1), dfs(i-1, j+time[i-1]) + cost[i-1])$
  • 若第 $i$ 面牆壁由免費油漆工繪製，則 $j$ 減去 $1$ 後遞迴；
  • 若第 $i$ 面牆壁由付費油漆工繪製，則 $j$ 加上 $time[i-1]$ 後遞迴，並將遞迴結果加上 $cost[i-1]$。
• 終止條件：$dfs(0, j) = 0$ if $j \geq 0$ else $\infty$
  • 終止時需要付費時間超過免費的時間，否則不合法，返回 $\infty$。
• 遞迴入口：$dfs(n, 0)$
• 剪枝：$j \geq i$ 時，表示免費油漆工可以繪製完剩餘的所有牆壁，返回 $0$ 。

複雜度分析

• 時間複雜度：$O(n^2)$ ，其中 $n$ 為牆壁數量，狀態數量為 $O(n^2)$ ，每個狀態需要 $O(1)$ 的時間計算。
• 空間複雜度：$O(n^2)$ ，狀態數量為 $O(n^2)$

PythonC++

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        n = len(cost)

        @cache
        def dfs(i: int, j: int) -> int:
            if j >= i:  # 剩餘的付費時間超過牆數
                return 0
            if i == 0:
                # return 0 if j >= 0 else float('inf') 
                return float('inf') # 已經檢查過 j >= i 的情況
            return min(dfs(i - 1, j - 1), # 免費刷第 i 堵牆 (下標為 i-1 )
                       dfs(i - 1, j + time[i - 1]) + cost[i - 1]) # 付費刷第 i 堵牆

        return dfs(n, 0)

class Solution {
public:
    int paintWalls(vector<int>& cost, vector<int>& time) {
        int n = cost.size();
        unordered_map<int, int> memo[n + 1]; // j can be negative, if use vector, need to shift
        function<int(int, int)> dfs = [&](int i, int j) {
            if (j >= i) return 0;
            if (i == 0) return INT_MAX / 2;  // avoid overflow
            if (memo[i].count(j)) return memo[i][j];
            return memo[i][j] = min(dfs(i - 1, j - 1),
                                    dfs(i - 1, j + time[i - 1]) + cost[i - 1]);
        };
        return dfs(n, 0);
    }
};

方法二：轉換為 0-1 背包問題

令付費油漆工的刷牆數量為 $paid$，工作時間為 $paid\_time$，免費油漆工的刷牆數量和工作時間為 $free = free\_time$ ，則根據題意， $paid + free = n$ ，且需要滿足 $paid\_time \geq free$。則可以得到 $paid\_time \geq n - paid$ ，移項得 $paid\_time + paid \geq n$。

則可以將問題轉換為 0-1 背包問題。將第 $i$ 面牆壁視為一個體積為 $time[i] + 1$ 、價值為 $cost[i]$ 的物品，背包容量為 $n$ 。問題等同於在背包容量為 $n$ 的情況下，選取物品使得總價值最小，並且體積至少等於背包容量。

令 $dfs(i, j)$ 表示考慮前 $i$ 面牆壁，且還需要的容量為 $j$ 的最小花費。對於第 $i$ 面牆壁，有選和不選兩種選擇，故可以得出以下遞迴式：

• $dfs(i, j) = min(dfs(i-1, j), dfs(i-1, j - (time[i-1] + 1)) + cost[i-1])$
  • 不選第 $i$ 面牆壁，則 $j$ 不變；
  • 選第 $i$ 面牆壁，則 $j$ 減去 $time[i-1] + 1$，並將遞迴結果加上 $cost[i-1]$。
• 終止條件：$dfs(0, j) = 0$ if $j \leq 0$ else $\infty$
  • 終止時需要的容量小於等於 $0$，返回 $0$，否則返回 $\infty$。
• 遞迴入口：$dfs(n, n)$
• 剪枝：$j \leq 0$ 時，表示已經選取了足夠的物品，故不用考慮後續物品，直接返回 $0$。

複雜度分析

• 時間複雜度：$O(n^2)$ ，其中 $n$ 為牆壁數量，狀態數量為 $O(n^2)$ ，每個狀態需要 $O(1)$ 的時間計算。
• 空間複雜度：$O(n^2)$ ，狀態數量為 $O(n^2)$ 。

PythonC++

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        n = len(cost)

        @cache  # Memoization
        def dfs(i: int, j: int) -> int:  # i: 已經考慮到第 i 堵牆，j: 還需要的體積
            if j <= 0:
                return 0
            if i == 0:
                return float('inf')
            return min(dfs(i - 1, j), # 不選
                       dfs(i - 1, j - (time[i - 1] + 1)) + cost[i - 1]) # 選
        
        return dfs(n, n)

class Solution {
public:
    int paintWalls(vector<int>& cost, vector<int>& time) {
        int n = cost.size();
        vector<vector<int>> memo(n + 1, vector<int>(n + 1, -1));
        function<int(int, int)> dfs = [&](int i, int j) {
            if (j <= 0) return 0;
            if (i == 0) return INT_MAX / 2; // avoid overflow
            if (memo[i][j] != -1) return memo[i][j];
            return memo[i][j] = min(dfs(i - 1, j),
                                    dfs(i - 1, j - time[i - 1] - 1) + cost[i - 1]);
        };
        return dfs(n, n);
    }
};

方法三：優化為一維空間

和方法二的思路相同，但注意到轉移時都只跟上一層有關，因此可以進一步優化空間複雜度。

需要注意，由於每個物品只能被使用一次，因此在更新 $dp[j]$ 時，需要從右到左更新，以避免重複使用同一物品。

複雜度分析

• 時間複雜度：$O(n^2)$ 。
• 空間複雜度：$O(n)$ 。

PythonC++

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        n = len(cost)
        dp = [float('inf') for _ in range(n + 1)]
        dp[0] = 0
        for c, t in zip(cost, time):
            for j in range(n, 0, -1):
                dp[j] = min(dp[j], dp[max(j - t - 1, 0)] + c)
        return dp[n]

class Solution {
public:
    int paintWalls(vector<int>& cost, vector<int>& time) {
        int n = cost.size();
        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] = min(dp[j], dp[max(j - time[i] - 1, 0)] + cost[i]);
        return dp[n];
    }
};

---

寫在最後

Cover photo is generated by @たろたろ, thanks for their work!