Ac solution code


  • 0

    The basic idea is:
    For each cost[i][0], we will choose minimum cost of the previous costs of the other two colors: costs[i-1][1], costs[i-1][2], then add the minimum cost to cost[i][0].

    Keep the above steps, finally return the minimum cost of costs[n-1][0], costs[n-1][1], costs[n-1][2].

    Time complexity: O(3n)=O(n)*

    public int minCost(int[][] costs) {
    	 if (costs == null || costs.length == 0)
    		 return 0;
    	 int n = costs.length;
    	 for (int i = 1; i < n; i++) {
    		 costs[i][0] += Math.min(costs[i-1][1], costs[i-1][2]);
    		 costs[i][1] += Math.min(costs[i-1][0], costs[i-1][2]);
    		 costs[i][2] += Math.min(costs[i-1][0], costs[i-1][1]);			 
    	 }
    	 return Math.min(costs[n-1][0], Math.min(costs[n-1][1], costs[n-1][2]));
     }

Log in to reply
 

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