首页 > 其他分享 >2024-04-03：用go语言，在一个小城市里，有 m 个房子排成一排， 你需要给每个房子涂上 n 种颜色之一（颜色编号为 1 到 n )， 有的房子去年夏天已经涂过颜色了，所以这些房子不可以被重新

2024-04-03：用go语言，在一个小城市里，有 m 个房子排成一排， 你需要给每个房子涂上 n 种颜色之一（颜色编号为 1 到 n )， 有的房子去年夏天已经涂过颜色了，所以这些房子不可以被重新

时间：2024-04-03 14:56:59浏览次数：25  
标签：涂过 颜色 target 房子 houses cost ans dp fill

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完整代码如下：

package main

import (
	"fmt"
	"math"
)

func minCost1(houses []int, cost [][]int, m int, n int, target int) int {
	dp := make([][][]int, m)
	for i := 0; i < m; i++ {
		dp[i] = make([][]int, target+1)
		for k := 0; k <= target; k++ {
			dp[i][k] = make([]int, n+1)
			for c := 0; c <= n; c++ {
				dp[i][k][c] = -1
			}
		}
	}
	ans := process1(houses, cost, n, 0, target, 0, dp)
	if ans == math.MaxInt32 {
		return -1
	}
	return ans
}

func process1(houses []int, cost [][]int, n, i, k, c int, dp [][][]int) int {
	if k < 0 {
		return math.MaxInt32
	}
	if i == len(houses) {
		if k == 0 {
			return 0
		}
		return math.MaxInt32
	}
	if dp[i][k][c] != -1 {
		return dp[i][k][c]
	}
	ans := math.MaxInt32
	if houses[i] != 0 {
		if houses[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 {
		for fill := 1; fill <= n; fill++ {
			var next int
			if fill == c {
				next = process1(houses, cost, n, i+1, k, fill, dp)
			} else {
				next = process1(houses, cost, n, i+1, k-1, fill, dp)
			}
			if next != math.MaxInt32 {
				ans = min(ans, cost[i][fill-1]+next)
			}
		}
	}
	dp[i][k][c] = ans
	return ans
}

func minCost2(houses []int, cost [][]int, m int, n int, target int) int {
	dp := make([][]int, target+1)
	for k := range dp {
		dp[k] = make([]int, n+1)
	}
	for c := 0; c <= n; c++ {
		dp[0][c] = 0
	}
	for k := 1; k <= target; k++ {
		for c := 0; c <= n; c++ {
			dp[k][c] = math.MaxInt32
		}
	}
	memo := make([]int, n+1)
	for i := m - 1; i >= 0; i-- {
		if houses[i] != 0 {
			houseColor := houses[i]
			for k := target; k >= 0; k-- {
				memory := dp[k][houseColor]
				for c := 0; c <= n; c++ {
					if houseColor != c {
						if k == 0 {
							dp[k][c] = math.MaxInt32
						} else {
							dp[k][c] = dp[k-1][houseColor]
						}
					} else {
						dp[k][c] = memory
					}
				}
			}
		} else {
			for k := target; k >= 0; k-- {
				for c := 0; c <= n; c++ {
					memo[c] = dp[k][c]
				}
				for c := 0; c <= n; c++ {
					ans := math.MaxInt32
					for fill := 1; fill <= n; fill++ {
						var next int
						if fill == c {
							next = memo[fill]
						} else {
							if k == 0 {
								next = math.MaxInt32
							} else {
								next = dp[k-1][fill]
							}
						}
						if next != math.MaxInt32 {
							ans = min(ans, cost[i][fill-1]+next)
						}
					}
					dp[k][c] = ans
				}
			}
		}
	}
	if dp[target][0] == math.MaxInt32 {
		return -1
	}
	return dp[target][0]
}

func minCost3(houses []int, cost [][]int, m int, n int, target int) int {
	dp := make([][]int, target+1)
	for k := range dp {
		dp[k] = make([]int, n+1)
	}
	for c := 0; c <= n; c++ {
		dp[0][c] = 0
	}
	for k := 1; k <= target; k++ {
		for c := 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]
	for i := m - 1; i >= 0; i-- {
		if houses[i] != 0 {
			for k, memory := target, 0; k >= 0; k-- {
				memory = dp[k][houses[i]]
				for c := 0; c <= n; c++ {
					if houses[i] != c {
						if k == 0 {
							dp[k][c] = math.MaxInt32
						} else {
							dp[k][c] = dp[k-1][houses[i]]
						}
					} else {
						dp[k][c] = memory
					}
				}
			}
		} else {
			for k := target; k >= 0; k-- {
				for c := 0; c <= n; c++ {
					memo[c] = dp[k][c]
				}
				for fill := 1; fill <= n; fill++ {
					if k == 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])
					}
				}
				for fill := n; fill >= 1; fill-- {
					if k == 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])
					}
				}
				for c, ans := 0, 0; c <= n; c++ {
					if c == 0 || memo[c] == math.MaxInt32 {
						ans = math.MaxInt32
					} else {
						ans = cost[i][c-1] + memo[c]
					}
					if c > 0 {
						ans = min(ans, minl[c-1])
					}
					if c < n {
						ans = min(ans, minr[c+1])
					}
					dp[k][c] = ans
				}
			}
		}
	}
	if dp[target][0] != math.MaxInt32 {
		return dp[target][0]
	}
	return -1
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	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-*-

import sys

def minCost1(houses, cost, m, n, target):
    dp = [[[-1] * (n + 1) for _ in range(target + 1)] for _ in range(m)]
    ans = process1(houses, cost, n, 0, target, 0, dp)
    if ans == sys.maxsize:
        return -1
    return ans

def process1(houses, cost, n, i, k, c, dp):
    if k < 0:
        return sys.maxsize
    if i == len(houses):
        if k == 0:
            return 0
        return sys.maxsize
    if dp[i][k][c] != -1:
        return dp[i][k][c]
    ans = sys.maxsize
    if houses[i] != 0:
        if houses[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:
        for fill in range(1, n + 1):
            if fill == c:
                next = process1(houses, cost, n, i + 1, k, fill, dp)
            else:
                next = process1(houses, cost, n, i + 1, k - 1, fill, dp)
            if next != sys.maxsize:
                ans = min(ans, cost[i][fill - 1] + next)
    dp[i][k][c] = ans
    return ans

def minCost2(houses, cost, m, n, target):
    dp = [[0] * (n + 1) for _ in range(target + 1)]
    for c in range(n + 1):
        dp[0][c] = 0
    for k in range(1, target + 1):
        for c in range(n + 1):
            dp[k][c] = sys.maxsize
    memo = [0] * (n + 1)
    for i in range(m - 1, -1, -1):
        if houses[i] != 0:
            houseColor = houses[i]
            for k in range(target, -1, -1):
                memory = dp[k][houseColor]
                for c in range(n + 1):
                    if houseColor != c:
                        if k == 0:
                            dp[k][c] = sys.maxsize
                        else:
                            dp[k][c] = dp[k - 1][houseColor]
                    else:
                        dp[k][c] = memory
        else:
            for k in range(target, -1, -1):
                for c in range(n + 1):
                    memo[c] = dp[k][c]
                for c in range(n + 1):
                    ans = sys.maxsize
                    for fill in range(1, n + 1):
                        if fill == c:
                            next = memo[fill]
                        else:
                            if k == 0:
                                next = sys.maxsize
                            else:
                                next = dp[k - 1][fill]
                        if next != sys.maxsize:
                            ans = min(ans, cost[i][fill - 1] + next)
                    dp[k][c] = ans
    if dp[target][0] == sys.maxsize:
        return -1
    return dp[target][0]

def minCost3(houses, cost, m, n, target):
    dp = [[0] * (n + 1) for _ in range(target + 1)]
    for c in range(n + 1):
        dp[0][c] = 0
    for k in range(1, target + 1):
        for c in range(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
    for i in range(m - 1, -1, -1):
        if houses[i] != 0:
            for k in range(target, -1, -1):
                memory = dp[k][houses[i]]
                for c in range(n + 1):
                    if houses[i] != c:
                        if k == 0:
                            dp[k][c] = sys.maxsize
                        else:
                            dp[k][c] = dp[k - 1][houses[i]]
                    else:
                        dp[k][c] = memory
        else:
            for k in range(target, -1, -1):
                for c in range(n + 1):
                    memo[c] = dp[k][c]
                for fill in range(1, n + 1):
                    if k == 0 or dp[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])
                for fill in range(n, 0, -1):
                    if k == 0 or dp[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])
                for c in range(n + 1):
                    if c == 0 or memo[c] == sys.maxsize:
                        ans = sys.maxsize
                    else:
                        ans = cost[i][c - 1] + memo[c]
                    if c > 0:
                        ans = min(ans, minl[c - 1])
                    if c < n:
                        ans = min(ans, minr[c + 1])
                    dp[k][c] = ans
    if dp[target][0] != sys.maxsize:
        return dp[target][0]
    return -1

def min(a, b):
    return a if a < b else b

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))

在这里插入图片描述

标签：涂过,颜色,target,房子,houses,cost,ans,dp,fill
From： https://www.cnblogs.com/moonfdd/p/18112684

相关文章

  • HTML——5.表单、框架、颜色
    一、表单HTML表单用于在网页中收集用户输入的数据，例如登录信息、搜索查询等。HTML提供了一系列的表单元素，允许用户输入文本、选择选项、提交数据等。<!DOCTYPEhtml><htmllang="en"><head>  <metacharset="UTF-8">  <metaname="viewport"content="width=......
  • 算法---动态规划练习-9（粉刷房子）
    题目1.题目解析2.讲解算法原理3.编写代码1.题目解析题目地址：点这里2.讲解算法原理创建dp表：vector<vector>dp(n,vector(3))。这里创建了一个二维向量dp，其中dp[i][j]表示第i天选择颜色j的最小成本。初始化第一天的成本：for(inti=0;i<3;i++)......
  • 男朋友在飞书被裁了，去年刚贷款在上海买了房子，每月房贷+房租就要1.2w，怎么办？
    作者|周天编辑|豆奶“飞书裁人”的消息传开后，很多社交平台的朋友都在讨论。毕竟在当下特殊时期，找工作不易，但裁人更难。更何况是大厂字节的飞书，这下很多人都悬了心。在社交媒体上，有不少网友已经在讨论这件事了。有的人才入职两个月，就已经接到通知了；有的人生怕被选中，正处于......
  • PCL点云处理之 点云垂直度计算与颜色渲染（二百三十八）
    PCL点云垂直度计算与颜色渲染（238）一、算法介绍二、垂直度的计算步骤与实现1.步骤描述2.代码示例三、基于垂直度的点云颜色渲染1.代码示例2.渲染效果四、参考文献一、算法介绍点云垂直度的计算方法：通过公式能知道地面，人行道、绿篱等位置的点云，法向......
  • LINUX颜色打印
     /////////////////////////////////////////////////////////////////////////////////////#defineD_RED"\e[0;31m"//#defineRED"\e[1;31m"//红#defineD_GREEN"\e[0;32m"//#defineGREE......
  • python 去除图片中指定颜色框或线
    目录Python去除图片中指定颜色框或线思路和步骤代码实现示例代码主要特点：一些常用功能：与OpenCV的区别：结语Python去除图片中指定颜色框或线在图像处理中，有时候我们需要对图片进行一些特定颜色框或线的处理，例如去除指定颜色的框或线。Python提供了强大的图像处理库Op......
  • C# 使用GDI 绘制三角形、圆形后并填充颜色
    C#使用GDI绘制三角形、圆形后并填充颜色privatevoidDrawBoneAgeAndAgeHeightPoint(Graphicsg,System.Drawing.PointFAgeHeight_Point,System.Drawing.PointFBoneAgePoint){System.Drawing.SolidBrushinnerBrush=newSystem.Drawing.SolidBrush(System.Drawi......
  • IDEA 代码字体大小 及 注释颜色 样式设置
    【本篇文章 参照的IDEA版本为2020】单击进入Settings【注释样式设置】按照1 2 3 4顺序找到注释的设置 功能作用详情见下图↓（也可以通过搜索框搜索）DIY颜色样本如下【代码字体大小设置】也在Editor里面 能找到上面的 就能看见这个font  一样的......
  • js计算线性渐变的中间颜色值
    可能会使用js计算线性渐变的中间颜色值，写个demo记录下<style>#colors{margin-top:2rem;display:flex;}#colorsdiv{width:100px;height:100px;}</style><divid="colors"><div></div><div></div&......
  • 前端学习-UI框架学习-Bootstrap5-005-颜色
    菜鸟教程学习链接字体颜色Bootstrap5提供了一些有代表意义的颜色类：.text-muted,.text-primary,.text-success,.text-info,.text-warning,.text-danger,.text-secondary,.text-white,.text-dark,.text-body(默认颜色，为黑色)and.text-light:可以设置文本颜色透明度......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99