Comment on page

# 256.Paint-House

## 题目描述

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.
Note:
All costs are positive integers.
Example:
Input: [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.

## 代码

### Approach #1 DFS With Memoization

class Solution {
public int minCost(int[][] costs) {
if (costs == null || costs.length == 0) return 0;
int[][] memo = new int[costs.length][costs[0].length];
return Math.min(dfs(0, 0, costs, memo),
Math.min(dfs(0, 1, costs, memo), dfs(0, 2, costs, memo)));
}
private int dfs(int n, int color, int[][] costs, int[][] memo) {
if (memo[n][color] > 0) {
return memo[n][color];
}
int totalCosts = costs[n][color];
if (n == costs.length - 1) {
} else if (color == 0) {
totalCosts += Math.min(dfs(n + 1, 1, costs, memo), dfs(n + 1, 2, costs, memo));
} else if (color == 1) {
totalCosts += Math.min(dfs(n + 1, 0, costs, memo), dfs(n + 1, 2, costs, memo));
} else if (color == 2) {
totalCosts += Math.min(dfs(n + 1, 0, costs, memo), dfs(n + 1, 1, costs, memo));
}
memo[n][color] = totalCosts;
}
}

### Approach #2 Dynamic Programming

class Solution {
public int minCost(int[][] costs) {
if (costs == null || costs.length == 0) return 0;
int n = costs.length;
int[][] dp = new int[n][3];
dp[0][0] = costs[0][0];
dp[0][1] = costs[0][1];
dp[0][2] = costs[0][2];
for (int i = 1; i < n; i++) {
dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + costs[i][0];
dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + costs[i][1];
dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + costs[i][2];
}
return Math.min(dp[n-1][0],
Math.min(dp[n-1][1], dp[n-1][2]));
}
}