# Ac solution code

• The basic idea is using DP algorithm to choose the minimum cost from (i - 1) house, then add it to costs[i][j] as minCosts[i][j] (To save space, we save minCosts[i][j] to costs[i][j] directly). A trick is to store two columns of top 2 minimum costs of (i - 1) row, to ensure we can choose one column isn't equal to j.

Runtime complexity = O(nk)

``````public int minCostII(int[][] costs) {
if (costs == null || costs.length == 0) return 0;
int n = costs.length, k = costs[0].length;
int min1 = -1, min2 = -1;
for (int i = 0; i < n; i++) {
int lastmin1 = min1, lastmin2 = min2;
min1 = min2 = -1;
for (int j = 0; j < k; j++) {
// Choose the index of the minimum cost from i - 1 row (exclude i)
if (lastmin1 != j)
costs[i][j] += (lastmin1 == -1) ? 0 : costs[i - 1][lastmin1];// Choose lastMin1
else
costs[i][j] += (lastmin2 == -1) ? 0 : costs[i - 1][lastmin2];// Choose lastMin2

if (min1 == -1 || costs[i][min1] > costs[i][j]) {// Update min1
min2 = min1;
min1 = j;
} else if (min2 == -1 || costs[i][min2] > costs[i][j]) {// Update min2
min2 = j;
}
}
}
return costs[n-1][min1];
}``````

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