Paint House III Solutions in C++

/// Source : https://leetcode.com/problems/paint-house-iii/
/// Author : liuyubobobo
/// Time   : 2020-06-06

#include <iostream>
#include <vector>

using namespace std;


/// Memory Search
/// Time Complexity: O(m^2 * n^2)
/// Space Complexity: O(m^2 * n)
class Solution {

private:
    int n;
    const int INF = 1e7;

public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {

        this->n = n;

        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n + 1, vector<int>(m + 1, -1)));
        int res = dfs(houses, 0, 0, target, cost, dp);
        return res == INF ? -1 : res;
    }

private:
    int dfs(const vector<int>& houses, int index, int precolor, int target,
            const vector<vector<int>>& cost, vector<vector<vector<int>>>& dp){

        if(target < 0) return INF;
        if(index == houses.size()) return target ? INF : 0;
        if(dp[index][precolor][target] != -1) return dp[index][precolor][target];

        int res = INF;
        if(!houses[index]){
            for(int i = 1; i <= n; i ++)
                res = min(res, cost[index][i - 1] + dfs(houses, index + 1, i, i == precolor ? target : target - 1, cost, dp));
        }
        else
            res = dfs(houses, index + 1, houses[index], houses[index] == precolor ? target : target - 1, cost, dp);

        return dp[index][precolor][target] = res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/paint-house-iii/
/// Author : liuyubobobo
/// Time   : 2020-06-06

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(m^2 * n^2)
/// Space Complexity: O(m^2 * n)
class Solution {

private:
    const int INF = 1e7;

public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {

        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n + 1, vector<int>(m + 1, INF)));

        if(!houses[0]) for(int color = 1; color <= n; color ++) dp[0][color][1] = cost[0][color - 1];
        else dp[0][houses[0]][1] = 0;

        for(int index = 1; index < m; index ++)
            for(int color = 1; color <= n; color ++)
                if(!houses[index] || houses[index] == color)
                    for(int precolor = 1; precolor <= n; precolor ++)
                        for(int k = 1; k <= target; k ++)
                            dp[index][color][k] = min(dp[index][color][k],
                                                      (houses[index] ? 0 : cost[index][color - 1]) + dp[index - 1][precolor][k - (precolor != color)]);

        int res = INF;
        for(int color = 1; color <= n; color ++) res = min(res, dp[m - 1][color][target]);
        return res == INF ? -1 : res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/paint-house-iii/
/// Author : liuyubobobo
/// Time   : 2020-06-06

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming + Rolling Array
/// Time Complexity: O(m^2 * n^2)
/// Space Complexity: O(m * n)
class Solution {

private:
    const int INF = 1e7;

public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {

        vector<vector<int>> dp(n + 1, vector<int>(m + 1, INF));

        if(!houses[0]) for(int color = 1; color <= n; color ++) dp[color][1] = cost[0][color - 1];
        else dp[houses[0]][1] = 0;

        for(int index = 1; index < m; index ++){

            vector<vector<int>> tdp(n + 1, vector<int>(m + 1, INF));

            for(int color = 1; color <= n; color ++)
                if(!houses[index] || houses[index] == color)
                    for(int precolor = 1; precolor <= n; precolor ++)
                        for(int k = 1; k <= target; k ++)
                            tdp[color][k] = min(tdp[color][k],
                                                (houses[index] ? 0 : cost[index][color - 1]) + dp[precolor][k - (precolor != color)]);
            dp = tdp;
        }

        int res = INF;
        for(int color = 1; color <= n; color ++) res = min(res, dp[color][target]);
        return res == INF ? -1 : res;
    }
};


int main() {

    return 0;
}