Java O(nk) Solution. DP + PriorityQueue


  • 0
    S
    public class Solution {
        public int minCostII(int[][] costs) {
            if(costs==null || costs.length==0||costs[0].length==0) return 0;
            if(costs[0].length==1) return costs[0][0];
            int n = costs.length;
            int k = costs[0].length;
            int[] total = new int[k];
            int min1 = 0;
            int min2 = 0;
            for(int i=0; i<n; i++){
                PriorityQueue<Integer> pq = new PriorityQueue<>();
                for(int j=0; j<k; j++){
                    int pre = (total[j]==min1? min2 : min1);
                    total[j] = costs[i][j] + pre;
                    pq.offer(total[j]);
                }
                min1 = pq.poll();
                min2 = pq.poll();
            }
            return min1;
        }
    }

Log in to reply
 

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