Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commite51583c

Browse files
committed
265 (1) min double-dp
1 parent6dd5dcb commite51583c

File tree

6 files changed

+565
-0
lines changed

6 files changed

+565
-0
lines changed

‎src/_265_PaintHouseII/Practice.java

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
/**
2+
* Time : O(nk) ; Space: O()
3+
* @tag : Dynamic Programming
4+
* @by : Steven Cooks
5+
* @date: Sep 28, 2015
6+
***************************************************************************
7+
* Description:
8+
*
9+
* There are a row of n houses, each house can be painted with one of the k colors.
10+
* The cost of painting each house with a certain color is different.
11+
* You have to paint all the houses such that no two adjacent houses have the same color.
12+
*
13+
* The cost of painting each house with a certain color is represented by a n x k cost matrix.
14+
*
15+
* For example, costs[0][0] is the cost of painting house 0 with color 0;
16+
* costs[1][2] is the cost of painting house 1 with color 2, and so on...
17+
* Find the minimum cost to paint all houses.
18+
*
19+
* Note: All costs are positive integers.
20+
*
21+
* Follow up: Could you solve it in O(nk) runtime?
22+
*
23+
***************************************************************************
24+
* {@link https://leetcode.com/problems/paint-house-ii/ }
25+
*/
26+
package_265_PaintHouseII;
27+
28+
/** see test {@link _265_PaintHouseII.PracticeTest } */
29+
publicclassPractice {
30+
31+
publicintminCostII(int[][]costs) {
32+
// TODO Auto-generated method stub
33+
return0;
34+
}
35+
36+
}

‎src/_265_PaintHouseII/Solution.java

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
/**
2+
* Time : O(nk) ; Space: O()
3+
* @tag : Dynamic Programming
4+
* @by : Steven Cooks
5+
* @date: Sep 28, 2015
6+
***************************************************************************
7+
* Description:
8+
*
9+
* There are a row of n houses, each house can be painted with one of the k colors.
10+
* The cost of painting each house with a certain color is different.
11+
* You have to paint all the houses such that no two adjacent houses have the same color.
12+
*
13+
* The cost of painting each house with a certain color is represented by a n x k cost matrix.
14+
*
15+
* For example, costs[0][0] is the cost of painting house 0 with color 0;
16+
* costs[1][2] is the cost of painting house 1 with color 2, and so on...
17+
* Find the minimum cost to paint all houses.
18+
*
19+
* Note: All costs are positive integers.
20+
*
21+
* Follow up: Could you solve it in O(nk) runtime?
22+
*
23+
***************************************************************************
24+
* {@link https://leetcode.com/problems/paint-house-ii/ }
25+
*/
26+
package_265_PaintHouseII;
27+
28+
/** see test {@link _265_PaintHouseII.SolutionTest } */
29+
publicclassSolution {
30+
31+
publicintminCostII(int[][]costs) {
32+
intn =costs.length;
33+
if (n ==0) {
34+
return0;
35+
}
36+
intk =costs[0].length;
37+
intmin1 =Integer.MAX_VALUE;// the smallest cost after paint i-th house
38+
intmin2 =Integer.MAX_VALUE;// second smallest cost
39+
intcolor = -1;// color for min1 choice in last round
40+
int[][]f =newint[n][k];
41+
for (inti =n -1;i >=0;i--) {
42+
inttemp1 =Integer.MAX_VALUE;
43+
inttemp2 =Integer.MAX_VALUE;
44+
inttempC = -1;
45+
for (intc =k -1;c >=0;c--) {
46+
intmincost =0;
47+
if (i ==n -1) {
48+
mincost =costs[i][c];
49+
}else {
50+
if (f[i][c] !=min1 &&color !=c) {
51+
mincost =min1 +costs[i][c];
52+
}else {
53+
mincost =min2 +costs[i][c];
54+
}
55+
}
56+
if (temp1 <=mincost) {
57+
temp2 =Math.min(temp2,mincost);
58+
}else {
59+
temp2 =temp1;
60+
temp1 =mincost;
61+
tempC =c;
62+
}
63+
f[i][c] =mincost;
64+
}
65+
min1 =temp1;
66+
min2 =temp2;
67+
color =tempC;
68+
}
69+
returnmin1;
70+
}
71+
72+
}
Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
/**
2+
* Time : O(nk*k) ; Space: O()
3+
* @tag : Dynamic Programming
4+
* @by : Steven Cooks
5+
* @date: Sep 28, 2015
6+
***************************************************************************
7+
* Description:
8+
*
9+
* There are a row of n houses, each house can be painted with one of the k colors.
10+
* The cost of painting each house with a certain color is different.
11+
* You have to paint all the houses such that no two adjacent houses have the same color.
12+
*
13+
* The cost of painting each house with a certain color is represented by a n x k cost matrix.
14+
*
15+
* For example, costs[0][0] is the cost of painting house 0 with color 0;
16+
* costs[1][2] is the cost of painting house 1 with color 2, and so on...
17+
* Find the minimum cost to paint all houses.
18+
*
19+
* Note: All costs are positive integers.
20+
*
21+
* Follow up: Could you solve it in O(nk) runtime?
22+
*
23+
***************************************************************************
24+
* {@link https://leetcode.com/problems/paint-house-ii/ }
25+
*/
26+
package_265_PaintHouseII;
27+
28+
/** see test {@link _265_PaintHouseII.SolutionSlowTest } */
29+
publicclassSolutionSlow {
30+
31+
// This version is slow because it takes extra O(k) time to find
32+
// max cost in the inner-most loop
33+
publicintminCostII(int[][]costs) {
34+
intn =costs.length;
35+
if (n ==0) {
36+
return0;
37+
}
38+
intk =costs[0].length;
39+
int[][]f =newint[n][k];
40+
for (inti =n -1;i >=0;i--) {
41+
for (intc =k -1;c >=0;c--) {
42+
intmincost =0;
43+
if (i ==n -1) {
44+
mincost =costs[i][c];
45+
}else {
46+
mincost =Integer.MAX_VALUE;
47+
for (intcolor =0;color <k;color++) {
48+
if (color !=c) {
49+
mincost =Math.min(mincost,f[i +1][color]);
50+
}
51+
}
52+
mincost +=costs[i][c];
53+
}
54+
f[i][c] =mincost;
55+
}
56+
}
57+
intres =Integer.MAX_VALUE;
58+
for (inti =0;i <k;i++) {
59+
res =Math.min(res,f[0][i]);
60+
}
61+
returnres;
62+
}
63+
64+
}
Lines changed: 131 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,131 @@
1+
package_265_PaintHouseII;
2+
3+
importstaticorg.junit.Assert.*;
4+
5+
importorg.junit.After;
6+
importorg.junit.Before;
7+
importorg.junit.Rule;
8+
importorg.junit.Test;
9+
importorg.junit.rules.Timeout;
10+
11+
publicclassPracticeTest {
12+
13+
/** Test method for {@link _265_PaintHouseII.Practice } */
14+
Practicesolution;
15+
16+
@Rule
17+
publicTimeoutglobalTimeout =newTimeout(200);
18+
19+
@Before
20+
publicvoidsetUp()throwsException {
21+
solution =newPractice();
22+
}
23+
24+
@After
25+
publicvoidtearDown()throwsException {
26+
solution =null;
27+
}
28+
29+
@Test
30+
publicvoidTest0() {
31+
int[][]costs = {
32+
{10,30,20 },
33+
};
34+
intactual =solution.minCostII(costs);
35+
intexpected =10;
36+
assertEquals(expected,actual);
37+
}
38+
39+
@Test
40+
publicvoidTest1() {
41+
int[][]costs = {
42+
{1,1,1 },
43+
{1,1,1 },
44+
{1,1,1 }
45+
};
46+
intactual =solution.minCostII(costs);
47+
intexpected =3;
48+
assertEquals(expected,actual);
49+
}
50+
51+
@Test
52+
publicvoidTest2() {
53+
int[][]costs = {
54+
{1,2,3 },
55+
{3,2,1 },
56+
{2,2,2 },
57+
{3,1,2 }
58+
};
59+
intactual =solution.minCostII(costs);
60+
intexpected =5;
61+
assertEquals(expected,actual);
62+
}
63+
64+
@Test
65+
publicvoidTest3() {
66+
int[][]costs = {
67+
{17,2,17 },
68+
{16,16,5 },
69+
{14,3,19 },
70+
};
71+
intactual =solution.minCostII(costs);
72+
intexpected =10;
73+
assertEquals(expected,actual);
74+
}
75+
76+
@Test
77+
publicvoidTest4() {
78+
int[][]costs = {
79+
{12,1,19 },
80+
{15,1,10 },
81+
{3,11,10 },
82+
{9,3,10 },
83+
{4,8,7 },
84+
{4,18,2 },
85+
{16,6,6 },
86+
{3,3,6 },
87+
{10,18,16 },
88+
{5,4,8 },
89+
{5,3,16 },
90+
{11,8,19 },
91+
{18,15,18 },
92+
{16,4,15 },
93+
{10,7,13 },
94+
{11,10,14 },
95+
{3,9,8 },
96+
{5,2,2 },
97+
{3,2,5 },
98+
{2,19,14 },
99+
{17,3,6 },
100+
{6,4,17 },
101+
{5,15,19 },
102+
{2,14,14 },
103+
{19,4,16 }
104+
};
105+
intactual =solution.minCostII(costs);
106+
intexpected =143;
107+
assertEquals(expected,actual);
108+
}
109+
110+
@Test
111+
publicvoidTest5() {
112+
int[][]costs = {
113+
{1,5,3 },
114+
{2,9,4 },
115+
};
116+
intactual =solution.minCostII(costs);
117+
intexpected =5;
118+
assertEquals(expected,actual);
119+
}
120+
121+
@Test
122+
publicvoidTest6() {
123+
int[][]costs = {
124+
{8 }
125+
};
126+
intactual =solution.minCostII(costs);
127+
intexpected =8;
128+
assertEquals(expected,actual);
129+
}
130+
131+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp