［抄题］：
There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.
The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.
[暴力解法]：
时间分析：
空间分析：
［奇葩输出条件］：
［奇葩corner case］：
［思维问题］：
以为要用i , j的二维矩阵：就3种情况，枚举所有情况就行了
［一句话思路］：
求和取前一步最小值，从而实现步步最小
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
- 理解过程：把所有值都累加到nums[n]中
［二刷］：
［三刷］：
［四刷］：
［五刷］：
[五分钟肉眼debug的结果]：
［总结］：
求和类型的三步dp，套用坐标型模板
［复杂度］：Time complexity: O(n) Space complexity: O(n)
［英文数据结构或算法，为什么不用别的数据结构或算法］：
［关键模板化代码］：
标准格式i = 0，i < n，return f[n - 1]
for (int i = 1; i < n; i++) { costs[i][0] += Math.min(costs[i - 1][1], costs[i - 1][2]); costs[i][1] += Math.min(costs[i - 1][0], costs[i - 1][2]); costs[i][2] += Math.min(costs[i - 1][0], costs[i - 1][1]); } //answer return Math.min(costs[n - 1][0], Math.min(costs[n - 1][1],costs[n - 1][2])); ［其他解法］：
［Follow Up］：
［LC给出的题目变变变］：
265. Paint House II 数学问题，感觉并没有什么联系
[代码风格] ：
public class Solution { /** * @param costs: n x 3 cost matrix * @return: An integer, the minimum cost to paint all houses */ public int minCost(int[][] costs) { //corner case if (costs.length == 0 || costs[0].length == 0) { return 0; } //get sum int n = costs.length; for (int i = 1; i < n; i++) { costs[i][0] += Math.min(costs[i - 1][1], costs[i - 1][2]); costs[i][1] += Math.min(costs[i - 1][0], costs[i - 1][2]); costs[i][2] += Math.min(costs[i - 1][0], costs[i - 1][1]); } //answer return Math.min(costs[n - 1][0], Math.min(costs[n - 1][1],costs[n - 1][2])); }}