房子题库

粉刷房子

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

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

例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。

请计算出粉刷完所有房子最少的花费成本。

示例1:

输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
     最少花费: 2 + 5 + 3 = 10。

示例2:

输入: costs = [[7,6,2]]
输出: 2

方案动态规划

思路:

状态定义: dp[i][j] 表示第i个房间染成颜色j的最小花费
状态转移方程: dp[i][k] = min {dp[i - 1][0 1 2 except k] + costs[i][k]}
初始状态: dp[0][k] = costs[0][k] 第一个房子都可以刷
问题答案
优化空间

:::details 点击查看代码

function minCost (costs) {
    let len=costs.length;
    if(len==0){
        return 0;
    }
    let result=costs[len-1];
    for(let i=len-2;i>=0;i--){
        let dp=[...costs[i]];
        dp[0]+=Math.min(result[1],result[2]);
        dp[1]+=Math.min(result[0],result[2]);
        dp[2]+=Math.min(result[0],result[1]);
        result=dp;
    }
    return Math.min(...result);
};

:::

性能分析:

时间复杂度：O(n)。
空间复杂度：O(1)。

粉刷房子 II

假如有一排房子，共 n 个，每个房子可以被粉刷成 k 种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

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

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

注意：

所有花费均为正整数。

示例1:

输入: [[1,5,3],[2,9,4]]
输出: 5
解释: 将 0 号房子粉刷成 0 号颜色，1 号房子粉刷成 2 号颜色。最少花费: 1 + 4 = 5; 
     或者将 0 号房子粉刷成 2 号颜色，1 号房子粉刷成 0 号颜色。最少花费: 3 + 2 = 5. 

方案动态规划

思路:

状态定义: dp[i][j] 表示第i个房间染成颜色j的最小花费
状态转移方程: dp[i][k] = min {dp[i - 1][0 1 2 except k] + costs[i][k]}
初始状态: dp[0][k] = costs[0][k] 第一个房子都可以刷
问题答案
优化空间

:::details 点击查看代码

function minCostII(costs) {
    let len=costs.length;
    if(len==0){
        return 0;
    }
    let colorNum=costs[0].length;
    let result=costs[len-1];
    for(let i=len-2;i>=0;i--){
        let dp=[...costs[i]];
        for(let j=0;j<colorNum;j++){
            dp[j]+=Math.min(...result.filter((value,index)=>index!==j));
        }
        result=dp;
    }
    return Math.min(...result);
};

:::

粉刷房子 III

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

我们将连续相同颜色尽可能多的房子称为一个街区。（比方说 houses = [1,2,2,3,3,2,1,1] ，它包含 5 个街区 [1, 2, 3, 2, 1] 。）

给你一个数组 houses ，一个 m * n 的矩阵 cost 和一个整数 target ，其中：

houses[i]：是第 i 个房子的颜色，0 表示这个房子还没有被涂色。 cost[i][j]：是将第 i 个房子涂成颜色 j+1 的花费。请你返回房子涂色方案的最小总花费，使得每个房子都被涂色后，恰好组成 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

方案动态规划

思路:

为了叙述方便，我们令所有的变量都从 00 开始编号，即：
- 房子的编号为 [0, m-1]；
- 颜色的编号为 [0, n-1]，如果房子没有涂上颜色，那么记为 -1；
- 街区的编号为 [0,target−1]。

状态定义:
- 设dp[i][j][k]表示将[0, i]的房子都涂上颜色，最末尾的第i个房子的颜色为j，并且它属于第k个街区时，需要的最少花费。
- 设best[i][j][k]表示所有的状态dp[i][j][k]中的最小值为first,取得最小值对应的j值为firstIndex,次小值为second
状态转移方程: 设第i-1个房子的颜色为j0,分类讨论出不同情况下的状态转移方程：
- 如果houses[i]!=-1&&houses[i]!=j, 方程为dp[i][j][k]=无穷大（不做任何处理，跳过）(说明: houses[i]!=-1,说明第i个房子已经涂过颜色了、house[i]!=j 说明已经重复涂色了)
- 否则:
  - 如果i=0时，如果k=0,则有方程:dp[i][j][k]=0(说明: i=0&&k=0 ,其实就是dp[0][j][0]=0)
  - 否则方程为dp[i][j][k]=dp[i-1][j][k]
    - 如果k>0,则dp[i][j][k]=min(dp[i][j][k],j==j0?dp[i-1][j][k]:dp[i-1][j0][k-1])
    - 通过best[i][j][k]可以快速的求出dp[i-1][j][k]和dp[i-1][j0][k-1]
      - best[i-1][k-1][0] 对应 dp[i-1][j0][k-1]
      - best[i-1][k-1][2] 对应 dp[i-1][j][k]
      - best[i-1][k-1][1] 对应 j0
  - 如果dp[i][j][k]!==Infinity&&house[i]===-1 ,则有方程dp[i][j][k]+=cost[i][j]
  - 用dp[i][j][k] 更新 best[i][j][k]
初始化状态:
- 调整颜色编号从0开始，没有被涂色标记为 -1
- dp 初始状态都为无穷大
- best 初始状态
  - best[i][j][1]=-1
问题答案: 最后返回 dp[m-1][j][target-1] 中的最小值

:::details 点击查看代码

function minCost(houses, cost, m, n, target) {
    for(let i=0;i<m;i++){
        houses[i]--;
    }
    let dp=new Array(m).fill(0).map(()=>new Array(n).fill(0).map(()=>new Array(target).fill(Infinity)));
    let best=new Array(m).fill(0).map(()=>new Array(target).fill(0).map(()=>new Array(3).fill(Infinity)));
    for(let i=0;i<m;i++){
        for(let j=0;j<target;j++){
            best[i][j][1]=-1;
        }
    }
    for(let i=0;i<m;i++){
        for(let j=0;j<n;j++){
            if(houses[i]!==-1&&houses[i]!==j){
                continue;
            }
            for(let k=0;k<target;k++){
                if(i==0){
                    if(k==0){
                        dp[i][j][k]=0;
                    }
                }else{
                    dp[i][j][k]=dp[i-1][j][k];
                    if(k>0){
                        const first=best[i-1][k-1][0];
                        const firstIndex=best[i-1][k-1][1];
                        const second=best[i-1][k-1][2];
                        dp[i][j][k]=Math.min(dp[i][j][k],j==firstIndex?second:first);
                    }
                }
                if(dp[i][j][k]!==Infinity&&houses[i]===-1){
                    dp[i][j][k]+=cost[i][j];
                }
                const first=best[i][k][0];
                const firstIndex=best[i][k][1];
                const second=best[i][k][2];
                if(dp[i][j][k]<first){
                    best[i][k][2]=first;
                    best[i][k][0]=dp[i][j][k];
                    best[i][k][1]=j;
                }else if(dp[i][j][k]<second){
                    best[i][k][2]=dp[i][j][k];
                }
            }
        }
    }
    let result=Infinity;
    for(let j=0;j<n;j++){
        result=Math.min(result,dp[m-1][j][target-1]);
    }
    return result==Infinity?-1:result;
};

:::

性能分析:

时间复杂度：O(m⋅n⋅target)。状态的数量为 O(m⋅n⋅target)，每个状态只需要 O(1) 的时间进行计算，同时需要 O(1) 的时间来更新 best，因此总时间复杂度为 O(m⋅n⋅target)。
空间复杂度：O(m⋅n⋅target)，即为状态的数量。除此之外，我们需要 O(m⋅target) 的空间存储 best，但其在渐进意义下小于前者，因此可以忽略。

安排邮筒

给你一个房屋数组houses 和一个整数 k ，其中 houses[i] 是第 i 栋房子在一条街上的位置，现需要在这条街上安排 k 个邮筒。

请你返回每栋房子与离它最近的邮筒之间的距离的最小总和。

答案保证在 32 位有符号整数范围以内。

示例1:

输入：houses = [1,4,8,10,20], k = 3
输出：5
解释：将邮筒分别安放在位置 3， 9 和 20 处。
每个房子到最近邮筒的距离和为 |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5 。

示例2:

输入：houses = [2,3,5,12,18], k = 2
输出：9
解释：将邮筒分别安放在位置 3 和 14 处。
每个房子到最近邮筒距离和为 |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9 。

方案动态规划

状态定义: dp[i][j] 表示给前i栋房子（从0开始编号）安排j个邮筒（从1开始编号）的最小距离总和
状态转移方程: 枚举第j个邮筒负责的房子的起始编号，从i0+1开始，到i结束。j 的范围为i0+1<j<=k&&<=i+1(j不会超过给定的邮筒数量并且不会超过房子数量)
- dp[i][j]=min(dp[i][j],dp[i0][j-1]+cost[i0+1][i])
- 边界条件: dp[i][1]=cost[0][i]
- cost[l][r] 表示给排好序的house[l]到house[r]的房子安排一个邮筒，可以得到的最小的距离总和。即cost[l][r] 为l和r的集合中的中位数，即cost[l][r]=cost[l+1][r-1]+house[r]-house[l]
初始状态: dp 元素初始为无穷大
问题答案: f[n−1][k]

:::details 点击查看代码

function minDistance(houses, k) {
    let len=houses.length;
    houses.sort((a,b)=>a-b);
    let cost=new Array(len).fill(0).map(()=>new Array(len).fill(0));
    for(let i=len-2;i>=0;i--){
        for(let j=i+1;j<len;j++){
            cost[i][j]=cost[i+1][j-1]+houses[j]-houses[i];
        }
    }
    let dp=new Array(len).fill(0).map(()=>new Array(k+1).fill(Infinity));
    for(let i=0;i<len;i++){
        dp[i][1]=cost[0][i];
        for(let j=2;j<=k&&j<=i+1;j++){
            for(let i0=0;i0<i;i0++){
                dp[i][j]=Math.min(dp[i][j],dp[i0][j-1]+cost[i0+1][i]);
            }
        }
    }
    return dp[len-1][k];
};

:::

性能分析:

时间复杂度：O(n^2k)
空间复杂度：O(n^2 + nk)

粉刷房子​

方案 动态规划​

粉刷房子 II​

方案 动态规划​

粉刷房子 III​

方案 动态规划​

安排邮筒​

方案 动态规划​

粉刷房子

方案动态规划

粉刷房子 II

方案动态规划

粉刷房子 III

方案动态规划

安排邮筒

方案动态规划