免费手机网站自助建站,免费下载代码的网站,住房和城乡建设部网站加装电梯,wordpress wp_loginout在一个小城市里#xff0c;有 m 个房子排成一排#xff0c;你需要给每个房子涂上 n 种颜色之一#xff08;颜色编号为 1 到 n #xff09;。有的房子去年夏天已经涂过颜色了#xff0c;所以这些房子不需要被重新涂色。
我们将连续相同颜色尽可能多的房子称为一个街区。有 m 个房子排成一排你需要给每个房子涂上 n 种颜色之一颜色编号为 1 到 n 。有的房子去年夏天已经涂过颜色了所以这些房子不需要被重新涂色。
我们将连续相同颜色尽可能多的房子称为一个街区。比方说 houses [1,2,2,3,3,2,1,1] 它包含 5 个街区 [{1}, {2,2}, {3,3}, {2}, {1,1}] 。
给你一个数组 houses 一个 m * n 的矩阵 cost 和一个整数 target 其中
houses[i]是第 i 个房子的颜色0 表示这个房子还没有被涂色。 cost[i][j]是将第 i 个房子涂成颜色 j1 的花费。 请你返回房子涂色方案的最小总花费使得每个房子都被涂色后恰好组成 target 个街区。如果没有可用的涂色方案请返回 -1 。
示例 1
输入houses [0,0,0,0,0], cost [[1,10],[10,1],[10,1],[1,10],[5,1]], m 5, n 2, target 3 输出9 解释房子涂色方案为 [1,2,2,1,1] 此方案包含 target 3 个街区分别是 [{1}, {2,2}, {1,1}]。 涂色的总花费为 (1 1 1 1 5) 9。 示例 2
输入houses [0,2,1,2,0], cost [[1,10],[10,1],[10,1],[1,10],[5,1]], m 5, n 2, target 3 输出11 解释有的房子已经被涂色了在此基础上涂色方案为 [2,2,1,2,2] 此方案包含 target 3 个街区分别是 [{2,2}, {1}, {2,2}]。 给第一个和最后一个房子涂色的花费为 (10 1) 11。 示例 3
输入houses [0,0,0,0,0], cost [[1,10],[10,1],[1,10],[10,1],[1,10]], m 5, n 2, target 5 输出5 示例 4
输入houses [3,1,2,3], cost [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m 4, n 3, target 3 输出-1 解释房子已经被涂色并组成了 4 个街区分别是 [{3},{1},{2},{3}] 无法形成 target 3 个街区。
解题思路
数组dp[i][j][k]中存储的元素含义是前i座房子并且第i座房子的颜色是j并且街区数目为k时产生的最小花费
代码解读
1.这段代码作用是将房子的颜色从0开始编号使得后面颜色的遍历直接从0开始 for (int i 0; i houses.length; i) {houses[i]--;}2.这段代码作用是初始化dp数组将全部元素置为最大值因为题目需要选出的时最小值因此没有填入元素的位置即为最大值后面在比较的时候就会失效 for (int i 0; i m ; i) {for(int j0;jn;j)Arrays.fill(dp[i][j],max);}3.状态转移 for (int i 0; i m ; i) {//遍历所有房子for(int j0;jn;j){//遍历所有颜色if(houses[i]!-1houses[i]!j) continue;
//条件等价于houses[i]-1||houses[i]j就直接下一轮循环
//houses[i]-1代表房子没上色houses[i]j代表当前房子已经上色并且颜色是j因为颜色已经固定了所以
//dp[i][j][k]只能在jhouses[i]的情况下填入元素颜色j等于其他值的情况是不可能出现for (int k 0; k target; k) {//遍历街区个数for (int p 0; p n; p) {//遍历前一个房子的颜色//先分为两种情况 //情况一前一个房子和当前房子同色//情况二前一个房子和当前房子不同色 if (pj)//情况一前一个房子和当前房子同色{if(i0)//1.当前房子是第一家因此不能从前一座房子转移状态{if(k0)//当前街区数只可能为0因为当前只有一家房子不可能产生k0 dp[i][j][k]0;}else{//2.当前房子不是第一家dp[i][j][k] Math.min(dp[i][j][k],dp[i-1][j][k]);//因为前一个房子和当前房子同色因此街区数是没有增加的颜色也是和前面房子的一样}}else if(i0k0){//情况二前一个房子和当前房子不同色dp[i][j][k] Math.min(dp[i][j][k],dp[i-1][p][k-1]);//因为当前房子和前一个房子颜色不一样因此需要产生一个新的街区}}if(houses[i]-1dp[i][j][k]!max)
//houses[i]-1代表房子没上色dp[i][j][k]!max 代表从前面的循环中是不能向dp[i][j][k]填入元素的
//例如 dp[0][j][k](k1) 这种情况是不可能出现的因此不能填入元素也不能在计算这种情况的花费dp[i][j][k]cost[i][j];}}}4.dp[m-1][i][target-1]m-1代表所有房子前m座房子target-1代表有target个街区i是最后一个房子的颜色找出最小值。 for (int i 0; i n; i) {res Math.min(res,dp[m-1][i][target-1]);}代码
class Solution {static int maxInteger.MAX_VALUE/2;public int minCost(int[] houses, int[][] cost, int m, int n, int target) {int[][][] dpnew int[m][n][target];for (int i 0; i houses.length; i) {houses[i]--;}for (int i 0; i m ; i) {for(int j0;jn;j)Arrays.fill(dp[i][j],max);}for (int i 0; i m ; i) {for(int j0;jn;j){if(houses[i]!-1houses[i]!j) continue;for (int k 0; k target; k) {for (int p 0; p n; p) {if (pj){if(i0){if(k0) dp[i][j][k]0;}else{dp[i][j][k] Math.min(dp[i][j][k],dp[i-1][j][k]);}}else if(i0k0){dp[i][j][k] Math.min(dp[i][j][k],dp[i-1][p][k-1]);}}if(houses[i]-1dp[i][j][k]!max)dp[i][j][k]cost[i][j];}}}int resmax;for (int i 0; i n; i) {res Math.min(res,dp[m-1][i][target-1]);}return resmax?-1:res;}
}
