Short Java solution using DP O(nk) running time


  • 0
    I

    The idea is similar to Paint House I. Initializing the variables with zeros since the costs are positive numbers.

    public class Solution {
        public int minCostII(int[][] costs) {
            if (costs == null || costs.length == 0 || costs[0].length == 0) return 0; 
            int min = 0;
            int minIndex = 0;
            int secMin = 0;
            for (int i = 0; i < costs.length; i++) {
                int newMin = 0;
                int newMinIndex = 0;
                int newSecMin = 0;
                for (int j = 0; j < costs[0].length; j++) {
                    int cost = costs[i][j] + ((minIndex != j) ? min : secMin);
                    if (newMin == 0 || cost < newMin) {
                        newSecMin = newMin;
                        newMin = cost;
                        newMinIndex = j;
                    } else if (newSecMin == 0 || cost < newSecMin) {
                        newSecMin = cost;
                    }
                }
                min = newMin;
                minIndex = newMinIndex;
                secMin = newSecMin;
            }
            return min;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.