6.1号刷题

发表于 | 分类于 | 0 comments

第一题 256. Paint House

算法

这题是动态规划的题目，主要采用的方法是将之前对应的每种选择的可能性的最小值都记录下来，然后不断向后更新。这样，每一次更新，只需要执行n次计算(利用之前存储的计算结果)，满足动态规划的算法定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class minCost256 {
    public int minCost(int[][] costs) {
        int n = costs.length;
        if (n == 0) return 0;
        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(Math.min(costs[n-1][0], costs[n-1][1]), costs[n-1][2]);
    }
}

第二题 265. Paint House II

算法

与前面一题类似，不过现在的情况变为了有k种颜色，主要方法不变。需要改变的部分是记录下上一个n的最小值的位置和最小值，在每次更新的时候可以用到。

下面的算法不是最优的，因为每次计算的时候，多消耗了O(k)的计算量寻找最小值。但是实际上我们可以在每次循环的时候就预先存储下来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class minCostII265 {
    public int minCostII(int[][] costs) {
        int n = costs.length;
        if (n == 0) return 0;
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            int firstMin = Integer.MAX_VALUE, secMin = Integer.MAX_VALUE, firstMinIndex = 0, secMinIndex = 0;
            //Find the minimum for i-1 len
            for (int k = 0; k < costs[0].length; k++) {
                if (costs[i-1][k] < firstMin && costs[i-1][k] < secMin) {
                    secMin = firstMin;
                    secMinIndex = firstMinIndex;
                    firstMin = costs[i-1][k];
                    firstMinIndex = k;
                } else if (costs[i-1][k] < secMin) {
                    secMin = costs[i-1][k];
                    secMinIndex = k;
                }
            }
            for (int j = 0; j < costs[0].length; j++) {
                if (j == firstMinIndex) {
                    costs[i][j] += secMin;
                } else {
                    costs[i][j] += firstMin;
                }
            }
        }
        for (int k = 0; k < costs[0].length; k++) {
            min = Math.min(costs[n-1][k], min);
        }
        return min;
    }
}