題目網址：https://leetcode.cn/problems/paint-house/

題意：假如有一排房子, 共 n 間, 每間房子可以被刷成紅、藍 、綠這三種顏色中的一種, 刷所有的房子, 並使其相鄰的兩間房子顏色不能相同。

由於市場上不同顏色的油漆其價格是不同的, 所以房子刷成不同顏色的成本也是不同的。每間房子刷成不同顏色的花費是以一個 n x 3 的正整數 matrix costs 來表示的。

e.g. costs[0][0] 表示第 0 號房子刷成紅色的成本；costs[1][2] 表示第 1 號房子刷成綠色的成本, 依此類推…

計算刷完所有房子所需的最少花費。

Solution 1：

想法：利用 DP

1. 定義狀態：

  • 首先, 會在 costs 前先加上 {0,0,0}, 代表什麼元素都沒有的狀態
  • dp[i][j] 為前 i 間房子中, 其中第 i 間房子刷成第 j 種顏色所需的最少成本

2. 得到狀態轉移方程：

  • dp[i][j] = min(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]) + costs[i][j]

若第 2 間房子刷成第 1 種顏色, 則第 1 間房子要選第 0 和 2 種顏色中成本較少的

➔ dp[2][1] = min(costs[1][2], costs[1][0]) + costs[2][1]

3. 初始化：

  • dp[0][j]：當沒有房子時, 將其刷成第 j 種顏色的最小成本為 0
  • dp[1][j]：當只有一間房子時, 將其刷成第 j 種顏色的最小成本為 cost[1][j]

e.g. costs = [[17,2,17],[16,16,5],[14,3,19]]

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        const int n = costs.size();
        vector<vector<int>> dp(n + 1, vector<int>(3, 0));

        costs.emplace(costs.begin(), vector<int>{0, 0, 0});
        dp[1] = costs[1];

        for (int i = 2; i <= n; ++i) {
            for (int j = 0; j < 3; ++j) {
                dp[i][j] = min(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]) + costs[i][j];
            }
        }

        return *min_element(dp[n].begin(), dp[n].end());
    }
};
  • time：$O(n)$ ➔ for loop 需 $O(3 \cdot n)$ time
  • space：$O(n)$ ➔ dp 需 $O(3 \cdot n)$ space

Solution 2：

想法：改進 Solution 1, 因為 dp[i][j] 只需用到第 i - 1 次的狀態, 因此只需儲存上一次的狀態即可, 根本不需要開到 $O(n)$ space

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        const int n = costs.size();

        costs.emplace(costs.begin(), vector<int>{0, 0, 0});
        vector<int> dp = costs[1];

        for (int i = 2; i <= n; ++i) {
            vector<int> nextRow(3, 0);
            for (int j = 0; j < 3; ++j) {
                nextRow[j] = min(dp[(j + 1) % 3], dp[(j + 2) % 3]) + costs[i][j];
            }
            dp = move(nextRow);
        }

        return *min_element(dp.begin(), dp.end());
    }
};
  • time：$O(n)$ ➔ for loop 需 $O(3 \cdot n)$ time
  • space：$O(1)$ ➔ dp, nextRow 只需 $O(3)$ space