求助一道算法题

问题描述：




假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子, 但是各个颜料是有限的, 红色能够粉刷n_r 房子, 绿色能够粉刷n_g房子, 蓝色能够粉刷n_b房子, 且n_r+n_g+n_b=n

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的矩阵来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。请你计算出粉刷完所有房子最少的花费成本。

思考方向：
dp最终实现O(n^3)

需要帮助的地方：
完全没有dp递推公式的思路, 只想到了列出所有可能的排列(有重复数字的全排列, 回溯+剪枝),,然后比较各个花费的大小, 但是这样的时间复杂度, 是O(n*n!) 太大了!!!!

引用
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/paint-house

救救孩子吧!!!!!!

主楼有个typo吧，是O(n*3) (也就是O(n))，O(n^3)就变成n的三次方啦

这个题bottom-up或者top-down都比较好想，看楼主习惯怎么写了，以bottom-up举例：
dp是一个3*n的数组，dp[i][j]表示把房子0-i都涂好颜色，并且房子i涂上颜色j所需要的最小总花费（“总”是指房子0-i的总和）

初始化
对于dp[0][0]，既然左边没有任何房子，dp[0][0]就是给0号房子刷颜色0的花费了，没有任何限制条件，dp[0][0] = cost[0][0]
dp[0][1], dp[0][2]同理

接下来考虑递推公式：对于i>=1，dp[i][0]该怎么算
如果想要给房子i刷颜色0，那么唯一的要求就是左侧的房子i-1不能是颜色0（注意我们是从左往右刷房子，所以管房子i-1就行不用管i+1）
那么只有两种情况：房子i-1是颜色1，或者房子i-1是颜色2
对应的花费分别是dp[i-1][1]，dp[i-1][2]
那么dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0]
dp[i][1], dp[i][2]同理

最后我们想要的是把所有房子涂好颜色的总花费的最小值
return min(dp[n-1]) 即可 （n是房子数量）

补充内容 (2021-06-09 16:11 +08:00):
编辑
看错题了 尴尬 😂

非常套路的DP。
令dp【i】【r】【g】[i]表示前i座房子刷出r个红色和g个绿色，所需要的最小代价。显然，前i座房子里刷出的蓝色的个数就是i-r-g（以1-index计数）。
状态转移的关键是第i座房子刷什么颜色，可以是红绿蓝的任意一种。所以

[i][i]dp【i】【r】【g】= min (dp[i-1][r-1][g] + cost[r], dp[i-1][r][g-1] + cost[g], dp[i-1][r][g] + cost)[/i]

[i]
最终的答案是在dp[n][r][g]中，遍历r和g，找到最小的值。特别注意，在dp【i】【r】【g】[i][i]的三重循环中，r、g、i-r-g都不能超过各自的上限nr、ng、nb。
[/i][/i][/i][/i][/i]

boruwang 发表于 2021-6-9 13:12
主楼有个typo吧，是O(n*3) (也就是O(n))，O(n^3)就变成n的三次方啦

这个题bottom-up或者top-down都比较 ...

是的是的，条件是n_r, n_g, n_b, 不是相邻的房子颜色不同，感谢回复啦！！！！！！！！

wisdompeak2 发表于 2021-6-9 15:51
非常套路的DP。
令dp【i】【r】【g】表示前i座房子刷出r个红色和g个绿色，所需要的最小代价。显然，前i座 ...

啊是的，之前没有想过可以增加dp array的维度，一直卡在怎么存储使用的颜料数量，感谢大佬！！

大概写了一下，求大米

1. 
   
2. int paintHouseDP(vector<vector<int>> cost, vector<int> count)
   
3. {
   
4.     int n = cost.size();
   
5.     vector<vector<vector<int>>> dp(count[0]+1, vector<vector<int>>(count[1]+1, vector<int>(count[2]+1, INT_MAX)));
   
6.     int res = INT_MAX;
   
7.     dp[0][0][0] = 0;
   
8.     for(int i=1; i<=n; ++i)
   
9.     {
   
10.         for(int r=0; r<=min(i, count[0]); ++r)
    
11.         {
    
12.             for(int g=0; g<=min(i-r, count[1]); ++g)
    
13.             {
    
14.                 int b = i-r-g;
    
15.                 if(b>count[2]) continue;
    
16.                 if(r) dp[r][g][b] = min(dp[r][g][b], dp[r-1][g][b]+cost[i-1][0]);
    
17.                 if(g) dp[r][g][b] = min(dp[r][g][b], dp[r][g-1][b]+cost[i-1][1]);
    
18.                 if(b) dp[r][g][b] = min(dp[r][g][b], dp[r][g][b-1]+cost[i-1][2]);
    
19.                 if(i==n) res = min(res, dp[r][g][b]);
    
20.             }
    
21.         }
    
22.     }
    
23.     return res;
    
24. }
    

复制代码