265. 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.

Follow up:
Could you solve it in O(nk) runtime?

Rust Solution

struct Solution;

impl Solution {
    fn min_cost_ii(costs: Vec<Vec<i32>>) -> i32 {
        let n = costs.len();
        if n == 0 {
            return 0;
        }
        let m = costs[0].len();
        let mut dp = vec![vec![0; m]; n];
        for i in 0..m {
            dp[0][i] = costs[0][i];
        }
        for i in 1..n {
            for j in 0..m {
                let mut min = std::i32::MAX;
                for k in 0..m {
                    if k != j {
                        min = min.min(dp[i - 1][k]);
                    }
                }
                dp[i][j] = costs[i][j] + min;
            }
        }
        dp[n - 1].iter().copied().min().unwrap()
    }
}

#[test]
fn test() {
    let costs = vec_vec_i32![[1, 5, 3], [2, 9, 4]];
    let res = 5;
    assert_eq!(Solution::min_cost_ii(costs), res);
}

Having problems with this solution? Click here to submit an issue on github.