LCR.P91[粉刷房子]

方法一：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int minCost(int[][] costs) {
        int red = 0, blue = 0, green = 0;
        for (int[] cost : costs) {
            int r = Math.min(blue, green) + cost[0];
            int b = Math.min(red, green) + cost[1];
            int g = Math.min(red, blue) + cost[2];

            red = r;
            blue = b;
            green = g;
        }
        return Math.min(red, Math.min(blue, green));
    }
}
  • 时间复杂度：$O(n \times C)$，其中$C = 3$
  • 空间复杂度：$O(1)$