多状态动态规划之粉刷房子

ゝ一纸荒年。 2024-03-17 12:27 102阅读 0赞

## 1. 题目分析 ##

题目链接选自力扣 : [剑指 Offer II 091. 粉刷房子][Offer II 091.]  
![image.png][]  
结合示例 1 来看 :  
![image.png][image.png 1]  
可以看到, 这个二维数组里的每一行代表一个房间, 有三个颜色, 每一行的 0 1 2 三列分别代表红、蓝、绿三个颜色. 里面的数值对应粉刷对应颜色的所需要的花费.

相邻房间不能同色, 同时还要最终粉刷完所有房间的花费最小.

## 2. 状态表示 ##

以 i 位置为结尾, 表示从第一个房间粉刷到第 i 个位置房间时所需要的最小花费.

对于最后 i 位置的房间, 其粉刷的房间颜色又有三种情况可以细分这个问题.

1.  i 位置房间最后粉刷为红色

这种情况我们用 dp\[i\]\[0\] 表示, 即从第一个房间粉刷到第 i 房间结束时, i 位置房间粉刷为红色所需要的最小花费

1.  i 位置房间最后粉刷为蓝色

这种情况我们用 dp\[i\]\[1\] 表示, 即从第一个房间粉刷到第 i 房间结束时, i 位置房间粉刷为蓝色所需要的最小花费

1.  i 位置房间最后粉刷为绿色

这种情况我们用 dp\[i\]\[2\] 表示, 即从第一个房间粉刷到第 i 房间结束时, i 位置房间粉刷为绿色所需要的最小花费

**这是一个典型的多状态动态规划问题, 而且比我们之前遇到的问题还多了一个状态表示.**

## 3. 状态转移方程 ##

这是一个多状态表示的问题, 因此它的状态转移方程也对应有多个. 分别来推导一下这三种情况.

1.  i 位置房间最后粉刷为红色

![image.png][image.png 2]  
当 i 位置被粉刷成红色时, i - 1 位置则不能粉刷为红色, 只能为蓝色或者绿色. 因此最终的最低花费为, 从第一个房间开始粉刷到第 i - 1 个房间为蓝色时的最小花费, 对应状态表示为 dp\[i-1\]\[1\]

或者 从第一个房间开始粉刷到第 i - 1 个房间为绿色时的最小花费, 对应状态表示为 dp\[i-1\]\[2\].

取得是最低花费, 因此为 Math.min( dp\[i-1\]\[1\], dp\[i-1\]\[2\] ), 最后加上 i 位置固定粉刷为红色的花费 costs\[i\]\[0\]

最终为 : **dp\[i\]\[0\] = Math.min( dp\[i-1\]\[1\], dp\[i-1\]\[2\] ) + costs\[i\]\[0\]**

1.  i 位置房间最后粉刷为蓝色

同理, **dp\[i\]\[1\] = Math.min( dp\[i-1\]\[0\], dp\[i-1\]\[2\] ) + costs\[i\]\[1\]**

1.  i 位置房间最后粉刷为绿色

同理, **dp\[i\]\[2\] = Math.min( dp\[i-1\]\[0\], dp\[i-1\]\[1\] ) + costs\[i\]\[2\]**

## 4. 初始化 ##

初始化是为了防止填表时发生越界错误, 根据状态转移方程来看, dp\[0\]\[0\] 和 dp\[0\]\[1\] 以及 dp\[0\]\[2\] 都需要初始化.

采取我们之前熟悉的新开一个格子的初始化方法.

**这里需要申明, 由于 costs 数组里面放的是每个房间不同颜色的花费, 我们把这个花费给看成一个值放到一维 dp 表中进行分析. 这个一维的 dp 表就表示每一个房间.值则为每个房间的最小花费 ! 并非实际创建一个一维 dp 表 ! ! !**

将原本旧 dp 表中的下标 0 位置数据放到新 dp 表中下标 1 位置的数据. 旧 dp 表中下标 1 位置的数据放到新 dp 表中下标 2 位置的数据. 以此类推. 这样就可以将原本的初始化( dp\[0\] )放到填表中 ( dp\[1\] ), 只需要初始化新的 dp 表的 dp\[0\] 即可.  
![在这里插入图片描述][489a85170aaf406dbecbadd11bf21467.png]  
那么, 新 dp 表的 dp\[0\] 位置该多少呢 ? 当只有一个房间的时候, 这个房间只有三种颜色可以粉刷, 红蓝绿. 最终的最小花费即为 costs\[0\]\[0\]. 只受本身房间粉刷颜色花费影响, 因此新的 dp 表中下标为 0 位置的值也应该为 0 不能影响 下标为 1 位置的值.

## 5. 填表顺序 ##

从状态转移方程来看, 想要填写 i 位置的最小花费, 就需要前一个位置的最小花费. 因此填表顺序为从左往右

## 6. 返回值 ##

根据题意, 求解粉刷到 n 房间时的最小花费, dp 表新开了一格, 大小为 n + 1. 根据状态转移方程, 到 n 房间时有三种情况, 因此返回这三种情况的最小花费即可. 最小花费即为 : **Math.min(dp\[n\]\[0\], dp\[n\]\[1\], dp\[n\]\[2\] )**

## 7. 代码演示 ##

class Solution {
        
        public int minCost(int[][] costs) {
        
            
            // 1. 创建 dp 表
            int n = costs.length; // 一共有多少个房间
            int[][] dp = new int[n + 1][3]; // 里面存的是 const[i][j] 每个房间不同颜色的花费
    
            // 2. 初始化
            dp[0][0] = 0;
    
            // 3. 填写 dp 表
            for(int i = 1; i <= n; i++) {
        
               
                // 这里的 for(int j = 0; j < 3; j++) 可以不写, 因为每一行的 0 1 2 三列是题目固定的
    
                // 根据状态转移方程填写
                // 需要注意的是, 因为对开了一格, 原本 costs 数组 0 下标对应在新的 dp 表中的 1 位置.
                // 想要从 dp 表中找到原本在 costs 数组中的位置, 下标都需要 - 1
                dp[i][0] = Math.min( dp[i-1][1], dp[i-1][2] ) + costs[i-1][0];
                dp[i][1] = Math.min( dp[i-1][0], dp[i-1][2] ) + costs[i-1][1];
                dp[i][2] = Math.min( dp[i-1][0], dp[i-1][1] ) + costs[i-1][2];
                
            }
    
            // 4. 确认返回值
            return Math.min(Math.min(dp[n][0], dp[n][1]), dp[n][2]);
        }
    }

[Offer II 091.]: https://leetcode.cn/problems/JEj789/
[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/a99c52b0a1bf41b8bfc09a02f259ffb8.png
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/206c7a13ea4d4b18bc984f82b5872c72.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/28f5f5e1cca24de69caa6460774bf073.png
[489a85170aaf406dbecbadd11bf21467.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/4d5865c358294784af464cc147c67eaa.png