文章目录

• 1. 题目
• 2. 解题

1. 题目

有n个房子在一列直线上，现在Bob需要给房屋染色，共有k种颜色。
每个房屋染不同的颜色费用也不同，Bob希望有一种染色方案使得相邻的房屋颜色不同。
但Bob计算了使相邻房屋颜色不同的最小染色费用，发现花费非常高。
于是Bob想选择一个区间作为主题步行街，在这个区间中的所有房子必须染成同一个颜色。Bob觉得这样可能能降低总花费，但是也不想让这个步行街太长。
Bob认为步行街的长度最多为 ‘t’。
但这个花费太难计算，Bob打算交给你来计算。
你能算出将这些房子进行染色的最小花费是多少吗？

费用通过一个nxk 的矩阵给出，比如costs[0][0]表示房屋0染颜色0的费用，costs[1][2]表示房屋1染颜色2的费用。
t 是一个整数，表示有最多有多少个房屋颜色相同。

房子总数: 1 <= n <= 100 
颜色总数: 1 <= k <= 100 
步行街长度上限: 1 <= t <= 10 
房屋染色费用: 1 <= cost[i][j] <= 1000

示例
样例1
输入:
costs = [[14,2,11],[11,14,5],[14,3,10]]
t = 2
输出: 10
说明:
三个屋子分别使用第1,2,1种颜色，总花费是10。
在这个样例中你不需要建造步行街。

样例2
输入:
costs = [[14,2,11],[11,14,5],[14,3,10]]
t = 2 
输出: 10
说明：
你可以在[1,2]的区间中建造一个步行街，
这样序号为1和2的两个房子可以染成相同颜色。
因此如果这三个房子的颜色为[2,2,1]，总花费为10.
如果你在[2,3]的区间中建造一个步行街，
最小的花费是11(1+5+5)，大于10，因此不是最优解。
你无法在[1,3]中建造步行街，因为步行街总长度为3，大于t。

来源：https://tianchi.aliyun.com/oj/15179470890799741/85251759933690470

2. 解题

题目意思是最多只能有一个步行街，我理解错了，以为是不限制

错误代码：

class Solution {
public:
    
    int paintHouseIII(vector<vector<int>> &costs, int t) {
        // Write your code here.
        int n = costs.size(), col = costs[0].size(), i, j;
        vector<vector<vector<int>>>  dp(n, vector<vector<int>>(col, vector<int>(t+1, INT_MAX)));
        // dp[i][c][k] 表示 i房子刷完了，其是 c 颜色，c 颜色连续了 k 次 的最小花费
        for(j = 0; j < col; ++j)
            dp[0][j][1] = costs[0][j];
        for(i = 1; i < n; ++i)
        {
            for(int c1 = 0; c1 < col; ++c1)
            {
                for(int c2 = 0; c2 < col; ++c2)
                {
                    if(c1 != c2)
                    {
                        for(int k = 1; k <= t; ++k)
                        {
                            if(dp[i-1][c1][k] == INT_MAX)
                                continue;
                            dp[i][c2][1] = min(dp[i][c2][1], costs[i][c2]+dp[i-1][c1][k]);
                        }
                    }
                    else
                    {
                        for(int k = 1; k < t; ++k)
                        {
                            if(dp[i-1][c1][k] == INT_MAX)
                                continue;
                            dp[i][c2][k+1] = min(dp[i][c2][k+1], costs[i][c2]+dp[i-1][c1][k]);
                        }
                    }
                    
                }
            }
        }
        int ans = INT_MAX;
        for(i = 0; i < col; ++i)
            for(j = 1; j <= t; ++j)
                ans = min(ans, dp[n-1][i][j]);
        return ans;
    }
};

参考大佬的题解：

正确解：

class Solution {
public:
    
    int paintHouseIII(vector<vector<int>> &costs, int t) {
        // Write your code here.
        int n = costs.size(), col = costs[0].size(), i, j, k, c1, c2;
        vector<vector<vector<int>>>  dp(n, vector<vector<int>>(col, vector<int>(2, INT_MAX)));
        // dp[i][c][0 or 1] 表示 i 房子刷完 c 颜色，还没有步行街0，有步行街1，的最小花费
        for(j = 0; j < col; ++j)
            dp[0][j][0] = dp[0][j][1] = costs[0][j];//初始化
        vector<vector<int>> value(n, vector<int>(n, 0));
        for(j = 0; j < col; ++j)
        {
            for(i = 0; i < n; ++i)//房子都刷 j 颜色的花费前缀和
            {
                if(i == 0)
                    value[i][j] = costs[i][j];
                else
                    value[i][j] = value[i-1][j] + costs[i][j];
            }
        }
        for(i = 1; i < n; ++i)
        {
            for(c1 = 0; c1 < col; ++c1)
            {
                for(c2 = 0; c2 < col; ++c2)
                {
                    if(c1 != c2)//颜色不一样
                    {
                        dp[i][c2][0] = min(dp[i][c2][0], dp[i-1][c1][0]+costs[i][c2]);
                        dp[i][c2][1] = min(dp[i][c2][1], dp[i-1][c1][1]+costs[i][c2]);
                    }
                }
                //颜色一样，可以跟前面组成步行街
                for(j = i-1; j >= 0; --j)//[j, i] 区间为同一颜色 c1 的步行街
                {
                    if(i-j+1 > t)
                        break;
                    dp[i][c1][1] = min(dp[i][c1][1], dp[j][c1][0]+value[i][c1]-value[j][c1]);
                    // 前面没有步行街0， + 加上后面都是 c1 颜色的花费
                }
            }
        }
        int ans = INT_MAX;
        for(j = 0; j < col; ++j)
            ans = min(ans, min(dp[n-1][j][0], dp[n-1][j][1]));
        return ans;
    }
};

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！