DayTwo

Question 1

Returns the minimum cost of building N houses with K different colors, with no two neighboring houses being the same color.

hint: matrix and dyn problem, use 2 loops

Answer 1

1) Dynamic programming problem
2) matrix problem loop twice one for rows which are houses here and one for columns which are colors here
3) try to find conditions to store the result.
4) use range with len function to loop through rows and columns.

greedy approach. since no 2 colors can be same so we need to carry forward best and second best answer to every row that is every house. along with the index of the best answer.

1) initialize row one with current values and store current best and second best
2) sum the current best to every row of next house except for same index position as first best store second best answer here.
3) store current house best and second best and continue.

4) last row will have final costs, take the minimum from there.

Question 2

Number of Ways to Paint N × 3 Grid

Hint: use dyn programming and math formula
3a + 2 b
2a + 2b

mod = 10**9+7

Answer 2

# twoColor and threeColor: note that Red, Blue and Green are used here 
        # (it is yellow, instead of blue in the problem description - which does not matter)

        # r g b = three colors, next rows can allow: use two colors ( g b g;  g r g) or use three colors ( g b r, b r g)
        # so, we have threeColor[i] = 2 * twoColor[i-1] + 2 * threeColor[i-1]

        # r g r = two colors, next rows can allow: use two colors (g b g; b r b; g r g) or use three colors (g r b, b r g)
        # so, we have twoColor[i] = 3 * twoColor[i-1] + 2 * threeColor[i-1]
1) use first row as reference, twocolor ways is 6 and threecolorways is 6
2) second row formula temp2= 3a+2b for twocolors
temp3=2a + 2b for 3 colors
twocolor,threecolor = temp2,temp3
3) loop for range(1,n) and return twocolor+threecolor

Question 3

3

Answer 3

3

Question 4

4

Answer 4

4

Question 5

5

Answer 5

5