Leetcode - Paint House II

https://leetcode.com/problems/paint-house-ii/

There are a row of n houses, each house can be painted with one of the k colors. 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 k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Example:

Input: [[1,5,3],[2,9,4]]
Output: 5
Explanation: Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5; 
             Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5. 

func minCostII(costs [][]int) int {
    if len(costs) == 0{
        return 0
    }
    n := len(costs)
    k := len(costs[0])
    dp := make([][]int, n)
    for i := 0; i < len(dp); i++ {
        dp[i] = make([]int, k)
    }
    for i := 0; i < k; i++ {
        dp[0][i] = costs[0][i]
    }
    for i := 1; i < n; i++ {
        for j := 0; j < k; j++ {
            dp[i][j] = costs[i][j] + getOther(dp[i-1], j)
        }
    }
    return min(dp[n-1])
}

func getOther(nums []int, idx int) int {
    minOther := math.MaxInt32
    for i, n := range nums {
        if i != idx && minOther > n {
            minOther = n
        }
    }
    return minOther
}

func min(nums []int) int {
    minNum := nums[0]
    for _, n := range nums {
        if n < minNum {
            minNum = n
        }
    }
    return minNum
}

• 相关文章
• 全局相关文章