256.Paint-House

256. Paint House

题目地址

https://leetcode.com/problems/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;
    return 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]));
  }
}