Paint House
给一个2d数组, 里面每个数组都是涂当前房子的三种颜色的花费. 求最少花费. 这个题求最小, 肯定是动态规划, 因为两个相邻的房子不能同色, 而且一共只有三种颜色, 所以我们每次涂一个后, 直接选剩下两个颜色中最小的cost的那个即可.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution { public int minCost(int[][] costs) { if(costs == null) return 0; if(costs.length == 0) return 0; for(int i = 1 ; i < costs.length; 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(Math.min(costs[costs.length - 1][0], costs[costs.length - 1][1]), costs[costs.length - 1][2]); } } |