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
| class Solution {
public int minCost(int[][] costs) {
Integer[][] cache = new Integer[costs.length][3];
int ans = Integer.MAX_VALUE;
for (int i = 0; i < costs[0].length; i++) {
ans = Math.min(ans, dfs(costs, 1, i, cache) + costs[0][i]);
}
return ans;
}
private int dfs(int[][] costs, int pos, int last, Integer[][] cache) {
if (pos == costs.length) {
return 0;
}
if (cache[pos][last] != null) {
return cache[pos][last];
}
int minimum = Integer.MAX_VALUE;
for (int i = 0; i < costs[pos].length; i++) {
if (i == last) {
continue;
}
minimum = Math.min(minimum, dfs(costs, pos + 1, i, cache) + costs[pos][i]);
}
return cache[pos][last] = minimum;
}
}
|
第一版, 就是recursion + memoization. 我们首先确定递归函数的功能. 这里定义的就是从某个位置, 如果该位置不能选某个颜色, 那么在此条件下, 递归函数告诉我们从该位置到最后一个位置的刷房子的minimum是多少. 为什么会有这个想法? 第0个房子, 如果刷成红色, 那么在第1个房子不能为红色的前提下, 如果我知道从第1个房子到最后一个房子刷墙的minimum, 那么我们就知道第0个房子是红色的前提下, 刷墙的minimum. 一样的道理, 我们也能知道第0个房子是蓝色或者第0个房子是绿色时, 刷墙的minimum. 这三种情况取最小值, 那就是答案.
于是递归函数功能确定. 由于遇到recursion, 难免会用到memoization. 这是因为某个情况会反复出现. 比如我第0个房子涂红色, 第1个房子涂绿色. 那么第2个房子就不能是绿色. 类似地, 第0个房子涂蓝色, 第1个房子涂绿色, 第2个房子也不能是绿色. 因此这个从第二个房子开始且不能涂绿色的求涂墙minimum这个case就被遇到了两次. 因此我们用一个cache来存状态.
按照我们之前的理论, 看递归函数的signature来判断cache是几维数组. 我们发现, 递归函数需要两个参数, pos也就是从哪个房子开始, last就是上个房子涂了什么颜色, 或者说我们此时不能涂什么颜色. 这两个变量决定了一个状态. 于是我们得出让cache被声明为二维数组. cache[i][j]表示从第i个房子开始, 且第i个房子不能是j这个颜色的前提下, 从第i个房子(inclusive)到最后一个房子涂墙的minimum. 这样recursion + memoization就出来了.
那base case是什么呢? 当我们涂完所有房子的时候, 即pos == costs.length的时候, 我们直接返回0即可. 因为此时没有房子涂了.
时间复杂度: O(n) 因为每个状态我们只会计算一次. 一共3 * n个状态, 3代表不能涂的颜色也就三种情况, n代表n个位置.
空间复杂度: O(n) 我们用一个二维数组来存计算过的结果.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int minCost(int[][] costs) {
int[][] dp = new int[costs.length][3];
dp[costs.length - 1][0] = Math.min(costs[costs.length - 1][1], costs[costs.length - 1][2]);
dp[costs.length - 1][1] = Math.min(costs[costs.length - 1][0], costs[costs.length - 1][2]);
dp[costs.length - 1][2] = Math.min(costs[costs.length - 1][0], costs[costs.length - 1][1]);
for (int i = costs.length - 2; i >= 0; i--) {
dp[i][0] = Math.min(dp[i + 1][1] + costs[i][1], dp[i + 1][2] + costs[i][2]);
dp[i][1] = Math.min(dp[i + 1][0] + costs[i][0], dp[i + 1][2] + costs[i][2]);
dp[i][2] = Math.min(dp[i + 1][0] + costs[i][0], dp[i + 1][1] + costs[i][1]);
}
return Math.min(dp[0][0], Math.min(dp[0][1], dp[0][2]));
}
}
|
第二版, 从recursion到memoization, 我们依旧按照我们的模板. 之前的逻辑就是如果当前是涂某个颜色, 那么如果知道后一个房子不涂该颜色前提下, 后面所有房子的minimum能知道, 那这就太好了. 把不能涂的三种情况的minimum都知道取最小即可.
此时的dp就是上一步的cache, dp[i][j]表示的状态一模一样. 那么我们得到的关系就是:
dp[i][0] = Math.min(dp[i + 1][1] + costs[i][1], dp[i + 1][2] + costs[i][2])
dp[i][1] = Math.min(dp[i + 1][0] + costs[i][0], dp[i + 1][2] + costs[i][2])
dp[i][2] = Math.min(dp[i + 1][0] + costs[i][0], dp[i + 1][1] + costs[i][1])
这就是状态转移方程. 当我们得到dp[0][0], dp[0][1]和dp[0][2]的时候, 我们求三者最小即可.
时间复杂度: O(n)
空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int minCost(int[][] costs) {
int[] dp = new int[3];
dp[0] = Math.min(costs[costs.length - 1][1], costs[costs.length - 1][2]);
dp[1] = Math.min(costs[costs.length - 1][0], costs[costs.length - 1][2]);
dp[2] = Math.min(costs[costs.length - 1][0], costs[costs.length - 1][1]);
for (int i = costs.length - 2; i >= 0; i--) {
int prevState0 = dp[0], prevState1 = dp[1], prevState2 = dp[2];
dp[0] = Math.min(prevState1 + costs[i][1], prevState2 + costs[i][2]);
dp[1] = Math.min(prevState0 + costs[i][0], prevState2 + costs[i][2]);
dp[2] = Math.min(prevState0 + costs[i][0], prevState1 + costs[i][1]);
}
return Math.min(dp[0], Math.min(dp[1], dp[2]));
}
}
|
最后一版. 我们发现dp[i]的三个状态只是依赖dp[i + 1]的三个状态. 于是我们就用三个变量记录即可. 当要更新当前新的i的三个状态的时候, 我们先把上一个状态存到三个变量里面. 然后用这三个变量更新当前的状态即可, 这样防止因为数据覆盖而丢失上一次的状态.
时间复杂度: O(n)
空间复杂度: O(1)
