1. 题目分析
题目链接选自力扣 : 剑指 Offer II 091. 粉刷房子
结合示例 1 来看 :
可以看到, 这个二维数组里的每一行代表一个房间, 有三个颜色, 每一行的 0 1 2 三列分别代表红、蓝、绿三个颜色. 里面的数值对应粉刷对应颜色的所需要的花费.
相邻房间不能同色, 同时还要最终粉刷完所有房间的花费最小.
2. 状态表示
以 i 位置为结尾, 表示从第一个房间粉刷到第 i 个位置房间时所需要的最小花费.
对于最后 i 位置的房间, 其粉刷的房间颜色又有三种情况可以细分这个问题.
- i 位置房间最后粉刷为红色
这种情况我们用 dp[i][0] 表示, 即从第一个房间粉刷到第 i 房间结束时, i 位置房间粉刷为红色所需要的最小花费
- i 位置房间最后粉刷为蓝色
这种情况我们用 dp[i][1] 表示, 即从第一个房间粉刷到第 i 房间结束时, i 位置房间粉刷为蓝色所需要的最小花费
- i 位置房间最后粉刷为绿色
这种情况我们用 dp[i][2] 表示, 即从第一个房间粉刷到第 i 房间结束时, i 位置房间粉刷为绿色所需要的最小花费
这是一个典型的多状态动态规划问题, 而且比我们之前遇到的问题还多了一个状态表示.
3. 状态转移方程
这是一个多状态表示的问题, 因此它的状态转移方程也对应有多个. 分别来推导一下这三种情况.
- i 位置房间最后粉刷为红色
当 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]
- i 位置房间最后粉刷为蓝色
同理, dp[i][1] = Math.min( dp[i-1][0], dp[i-1][2] ) + costs[i][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] 即可.
那么, 新 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]); } }
