2024-04-03:用go语言,在一个小城市里,有 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 个房子涂成颜色 j+1 的花费。
请你返回房子涂色方案的最小总花费,使得每个房子都被涂色后,恰好组成 target 个街区。
如果没有可用的涂色方案,请返回 -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。
答案2024-04-03:
来自左程云。
灵捷3.5
大体步骤如下:
minCost1函数:
1.首先,创建一个三维数组dp,用于记录状态转移的结果。dp[i][k][c]表示将前i个房子涂色,形成k个街区,并且第i个房子颜色为c+1时的最小总花费。
2.然后,调用process1函数,进行递归计算。
3.在process1函数中,首先处理边界情况:如果k小于0,返回无穷大;如果i等于房子数量,如果k等于0,返回0,否则返回无穷大。
4.如果dp[i][k][c]已经计算过,直接返回结果。
5.接着,判断第i个房子的颜色是否已经确定(houses[i] != 0):
- •如果颜色已经确定,判断该颜色是否与c相同,分别递归处理下一个房子(i+1)和剩余街区数量(k-1或k)。
- •如果颜色未确定,遍历每种可能的颜色(1到n),分别递归处理下一个房子和剩余街区数量,并记录选择花费最小的方案。
6.将结果存入dp[i][k][c],并返回结果。
minCost2函数:
1.创建一个二维数组dp,用于记录状态转移的结果。dp[k][c]表示形成k个街区,且最后一个房子颜色为c+1时的最小总花费。
2.首先初始化dp数组:对于k=0(没有街区)和所有的颜色c,花费为0;对于k>0和所有的颜色c,花费初始化为无穷大。
3.然后,从后向前遍历房子,处理每个房子的情况:
- •如果房子颜色已经确定(houses[i] != 0),更新dp数组中对应位置的值。
- •如果房子颜色未确定,通过dp数组中记录的上一次的结果,计算每个街区数量和颜色的最小花费,更新dp数组中对应位置的值。
4.最后,返回dp[target][0]的结果,如果为无穷大则返回-1。
minCost3函数:
1.创建一个二维数组dp,用于记录状态转移的结果。dp[k][c]表示形成k个街区,且最后一个房子颜色为c+1时的最小总花费。
2.首先初始化dp数组和辅助数组minl和minr:
- •对于k=0(没有街区)和所有的颜色c,花费为0;
- •对于k>0和所有的颜色c,花费初始化为无穷大;
- •minl[i]表示前i个颜色中最小的花费,minr[i]表示从第i个颜色到第n个颜色中最小的花费。
3.然后,从后向前遍历房子,处理每个房子的情况:
- •如果房子颜色已经确定(houses[i] != 0),更新dp数组中对应位置的值。
- •如果房子颜色未确定,通过dp数组中记录的上一次的结果和辅助数组minl和minr,计算每个街区数量和颜色的最小花费,更新dp数组中对应位置的值。
4.最后,返回dp[target][0]的结果,如果为无穷大则返回-1。
这3种算法的时间复杂度和空间复杂度如下:
- •minCost1:时间复杂度为O(m * n^target),空间复杂度为O(m * target * n)。
- •minCost2:时间复杂度为O(m * target * n^2),空间复杂度为O(target * n)。
- •minCost3:时间复杂度为O(m * target * n^2),空间复杂度为O(n)。
Go完整代码如下:
packagemain
import(
"fmt"
"math"
)
funcminCost1(houses[]int,cost[][]int,mint,nint,targetint)int{
dp:=make([][][]int,m)
fori:=0;idp[i]=make([][]int,target+1)
fork:=0;k<=target;k++{
dp[i][k]=make([]int,n+1)
forc:=0;c<=n;c++{
dp[i][k][c]=-1
}
}
}
ans:=process1(houses,cost,n,0,target,0,dp)
ifans==math.MaxInt32{
return-1
}
returnans
}
funcprocess1(houses[]int,cost[][]int,n,i,k,cint,dp[][][]int)int{
ifk<0{
returnmath.MaxInt32
}
ifi==len(houses){
ifk==0{
return0
}
returnmath.MaxInt32
}
ifdp[i][k][c]!=-1{
returndp[i][k][c]
}
ans:=math.MaxInt32
ifhouses[i]!=0{
ifhouses[i]!=c{
ans=process1(houses,cost,n,i+1,k-1,houses[i],dp)
}else{
ans=process1(houses,cost,n,i+1,k,houses[i],dp)
}
}else{
forfill:=1;fill<=n;fill++{
varnextint
iffill==c{
next=process1(houses,cost,n,i+1,k,fill,dp)
}else{
next=process1(houses,cost,n,i+1,k-1,fill,dp)
}
ifnext!=math.MaxInt32{
ans=min(ans,cost[i][fill-1]+next)
}
}
}
dp[i][k][c]=ans
returnans
}
funcminCost2(houses[]int,cost[][]int,mint,nint,targetint)int{
dp:=make([][]int,target+1)
fork:=rangedp{
dp[k]=make([]int,n+1)
}
forc:=0;c<=n;c++{
dp[0][c]=0
}
fork:=1;k<=target;k++{
forc:=0;c<=n;c++{
dp[k][c]=math.MaxInt32
}
}
memo:=make([]int,n+1)
fori:=m-1;i>=0;i--{
ifhouses[i]!=0{
houseColor:=houses[i]
fork:=target;k>=0;k--{
memory:=dp[k][houseColor]
forc:=0;c<=n;c++{
ifhouseColor!=c{
ifk==0{
dp[k][c]=math.MaxInt32
}else{
dp[k][c]=dp[k-1][houseColor]
}
}else{
dp[k][c]=memory
}
}
}
}else{
fork:=target;k>=0;k--{
forc:=0;c<=n;c++{
memo[c]=dp[k][c]
}
forc:=0;c<=n;c++{
ans:=math.MaxInt32
forfill:=1;fill<=n;fill++{
varnextint
iffill==c{
next=memo[fill]
}else{
ifk==0{
next=math.MaxInt32
}else{
next=dp[k-1][fill]
}
}
ifnext!=math.MaxInt32{
ans=min(ans,cost[i][fill-1]+next)
}
}
dp[k][c]=ans
}
}
}
}
ifdp[target][0]==math.MaxInt32{
return-1
}
returndp[target][0]
}
funcminCost3(houses[]int,cost[][]int,mint,nint,targetint)int{
dp:=make([][]int,target+1)
fork:=rangedp{
dp[k]=make([]int,n+1)
}
forc:=0;c<=n;c++{
dp[0][c]=0
}
fork:=1;k<=target;k++{
forc:=0;c<=n;c++{
dp[k][c]=math.MaxInt32
}
}
memo:=make([]int,n+1)
minl:=make([]int,n+2)
minr:=make([]int,n+2)
minr[n+1]=math.MaxInt32
minl[n+1]=minr[n+1]
minr[0]=minl[n+1]
minl[0]=minr[0]
fori:=m-1;i>=0;i--{
ifhouses[i]!=0{
fork,memory:=target,0;k>=0;k--{
memory=dp[k][houses[i]]
forc:=0;c<=n;c++{
ifhouses[i]!=c{
ifk==0{
dp[k][c]=math.MaxInt32
}else{
dp[k][c]=dp[k-1][houses[i]]
}
}else{
dp[k][c]=memory
}
}
}
}else{
fork:=target;k>=0;k--{
forc:=0;c<=n;c++{
memo[c]=dp[k][c]
}
forfill:=1;fill<=n;fill++{
ifk==0||dp[k-1][fill]==math.MaxInt32{
minl[fill]=minl[fill-1]
}else{
minl[fill]=min(minl[fill-1],cost[i][fill-1]+dp[k-1][fill])
}
}
forfill:=n;fill>=1;fill--{
ifk==0||dp[k-1][fill]==math.MaxInt32{
minr[fill]=minr[fill+1]
}else{
minr[fill]=min(minr[fill+1],cost[i][fill-1]+dp[k-1][fill])
}
}
forc,ans:=0,0;c<=n;c++{
ifc==0||memo[c]==math.MaxInt32{
ans=math.MaxInt32
}else{
ans=cost[i][c-1]+memo[c]
}
ifc>0{
ans=min(ans,minl[c-1])
}
ifcans=min(ans,minr[c+1])
}
dp[k][c]=ans
}
}
}
}
ifdp[target][0]!=math.MaxInt32{
returndp[target][0]
}
return-1
}
funcmin(a,bint)int{
ifareturna
}
returnb
}
funcmain(){
houses:=[]int{0,0,0,0,0}
cost:=[][]int{{1,10},{10,1},{10,1},{1,10},{5,1}}
m:=5
n:=2
target:=3
fmt.Println(minCost1(houses,cost,m,n,target))
fmt.Println(minCost2(houses,cost,m,n,target))
fmt.Println(minCost3(houses,cost,m,n,target))
}
Python完整代码如下:
#-*-coding:utf-8-*-
importsys
defminCost1(houses,cost,m,n,target):
dp=[[[-1]*(n+1)for_inrange(target+1)]for_inrange(m)]
ans=process1(houses,cost,n,0,target,0,dp)
ifans==sys.maxsize:
return-1
returnans
defprocess1(houses,cost,n,i,k,c,dp):
ifk<0:
returnsys.maxsize
ifi==len(houses):
ifk==0:
return0
returnsys.maxsize
ifdp[i][k][c]!=-1:
returndp[i][k][c]
ans=sys.maxsize
ifhouses[i]!=0:
ifhouses[i]!=c:
ans=process1(houses,cost,n,i+1,k-1,houses[i],dp)
else:
ans=process1(houses,cost,n,i+1,k,houses[i],dp)
else:
forfillinrange(1,n+1):
iffill==c:
next=process1(houses,cost,n,i+1,k,fill,dp)
else:
next=process1(houses,cost,n,i+1,k-1,fill,dp)
ifnext!=sys.maxsize:
ans=min(ans,cost[i][fill-1]+next)
dp[i][k][c]=ans
returnans
defminCost2(houses,cost,m,n,target):
dp=[[0]*(n+1)for_inrange(target+1)]
forcinrange(n+1):
dp[0][c]=0
forkinrange(1,target+1):
forcinrange(n+1):
dp[k][c]=sys.maxsize
memo=[0]*(n+1)
foriinrange(m-1,-1,-1):
ifhouses[i]!=0:
houseColor=houses[i]
forkinrange(target,-1,-1):
memory=dp[k][houseColor]
forcinrange(n+1):
ifhouseColor!=c:
ifk==0:
dp[k][c]=sys.maxsize
else:
dp[k][c]=dp[k-1][houseColor]
else:
dp[k][c]=memory
else:
forkinrange(target,-1,-1):
forcinrange(n+1):
memo[c]=dp[k][c]
forcinrange(n+1):
ans=sys.maxsize
forfillinrange(1,n+1):
iffill==c:
next=memo[fill]
else:
ifk==0:
next=sys.maxsize
else:
next=dp[k-1][fill]
ifnext!=sys.maxsize:
ans=min(ans,cost[i][fill-1]+next)
dp[k][c]=ans
ifdp[target][0]==sys.maxsize:
return-1
returndp[target][0]
defminCost3(houses,cost,m,n,target):
dp=[[0]*(n+1)for_inrange(target+1)]
forcinrange(n+1):
dp[0][c]=0
forkinrange(1,target+1):
forcinrange(n+1):
dp[k][c]=sys.maxsize
memo=[0]*(n+1)
minl=[sys.maxsize]*(n+2)
minr=[sys.maxsize]*(n+2)
minl[n+1]=minr[n+1]=sys.maxsize
minl[0]=minr[0]=sys.maxsize
foriinrange(m-1,-1,-1):
ifhouses[i]!=0:
forkinrange(target,-1,-1):
memory=dp[k][houses[i]]
forcinrange(n+1):
ifhouses[i]!=c:
ifk==0:
dp[k][c]=sys.maxsize
else:
dp[k][c]=dp[k-1][houses[i]]
else:
dp[k][c]=memory
else:
forkinrange(target,-1,-1):
forcinrange(n+1):
memo[c]=dp[k][c]
forfillinrange(1,n+1):
ifk==0ordp[k-1][fill]==sys.maxsize:
minl[fill]=minl[fill-1]
else:
minl[fill]=min(minl[fill-1],cost[i][fill-1]+dp[k-1][fill])
forfillinrange(n,0,-1):
ifk==0ordp[k-1][fill]==sys.maxsize:
minr[fill]=minr[fill+1]
else:
minr[fill]=min(minr[fill+1],cost[i][fill-1]+dp[k-1][fill])
forcinrange(n+1):
ifc==0ormemo[c]==sys.maxsize:
ans=sys.maxsize
else:
ans=cost[i][c-1]+memo[c]
ifc>0:
ans=min(ans,minl[c-1])
ifcans=min(ans,minr[c+1])
dp[k][c]=ans
ifdp[target][0]!=sys.maxsize:
returndp[target][0]
return-1
defmin(a,b):
returnaifa
houses=[0,0,0,0,0]
cost=[[1,10],[10,1],[10,1],[1,10],[5,1]]
m=5
n=2
target=3
print(minCost1(houses,cost,m,n,target))
print(minCost2(houses,cost,m,n,target))
print(minCost3(houses,cost,m,n,target))
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.