There is a row of N houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. Find the minimum cost to paint all houses.
The cost of painting each house in red, blue or green colour is given in the array r[], g[] and b[] respectively.
Example 1:
Input:
N = 3
r[] = {1, 1, 1}
g[] = {2, 2, 2}
b[] = {3, 3, 3}
Output: 4
Explanation: We can color the houses 
in RGR manner to incur minimum cost.
We could have obtained a cost of 3 if 
we coloured all houses red, but we 
cannot color adjacent houses with 
the same color.
Example 2:
Input:
N = 3
r[] = {2, 1, 3}
g[] = {3, 2, 1}
b[] = {1, 3, 2} 
Output: 3
Explanation: We can color the houses
in BRG manner to incur minimum cost.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function distinctColoring() which takes the size N and the color arrays r[], g[], b[] as input parameters and returns the minimum cost of coloring such that the color of no two houses is same.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 5*10^{4}
1 <= r[i], g[i], b[i] <= 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def distinctColoring (self, N, r, g, b):

        # code here 

        

        

Solutions:
class Solution:

	def distinctColoring(self, N, r, g, b):
		dp = [[0] * 3 for _ in range(N)]
		dp[0][0] = r[0]
		dp[0][1] = g[0]
		dp[0][2] = b[0]
		for i in range(1, N):
			dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + r[i]
			dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + g[i]
			dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + b[i]
		return min(dp[N - 1])


class Solution:

	def distinctColoring(self, N, r, g, b):
		arr = [r, g, b]
		for i in range(N - 2, -1, -1):
			arr[0][i] += min(arr[1][i + 1], arr[2][i + 1])
			arr[1][i] += min(arr[0][i + 1], arr[2][i + 1])
			arr[2][i] += min(arr[1][i + 1], arr[0][i + 1])
		return min(arr[0][0], arr[1][0], arr[2][0])


class Solution:

	def distinctColoring(self, N, r, g, b):
		for i in range(1, N):
			r[i] = r[i] + min(g[i - 1], b[i - 1])
			g[i] = g[i] + min(r[i - 1], b[i - 1])
			b[i] = b[i] + min(r[i - 1], g[i - 1])
		return min(r[N - 1], g[N - 1], b[N - 1])


import sys
sys.setrecursionlimit(100000)

class Solution:

	def distinctColoring(self, N, r, g, b):
		dp = [[0 for i in range(3)] for _ in range(N)]
		dp[0][0] = r[0]
		dp[0][1] = g[0]
		dp[0][2] = b[0]
		for i in range(1, N):
			dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + r[i]
			dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + g[i]
			dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + b[i]
		return min(dp[N - 1][0], dp[N - 1][1], dp[N - 1][2])


inf = 10 ** 18

class Solution:

	def distinctColoring(self, n, r, g, b):
		dp = [[0 for i in range(3)] for j in range(n)]
		dp[0][0] = r[0]
		dp[0][1] = g[0]
		dp[0][2] = b[0]
		for i in range(1, n):
			dp[i][0] = r[i] + min(dp[i - 1][1], dp[i - 1][2])
			dp[i][1] = g[i] + min(dp[i - 1][0], dp[i - 1][2])
			dp[i][2] = b[i] + min(dp[i - 1][1], dp[i - 1][0])
		return min(dp[n - 1][0], min(dp[n - 1][1], dp[n - 1][2]))


class Solution:

	def distinctColoring(self, N, r, g, b):
		dp = []
		tp = [0, 0, 0]
		(tp[0], tp[1], tp[2]) = (r[0], g[0], b[0])
		dp.append(tp)
		for i in range(1, N):
			tp = [0, 0, 0]
			tp[0] = r[i] + min(dp[i - 1][1], dp[i - 1][2])
			tp[1] = g[i] + min(dp[i - 1][0], dp[i - 1][2])
			tp[2] = b[i] + min(dp[i - 1][0], dp[i - 1][1])
			dp.append(tp)
		k = int(min(dp[N - 1][0], dp[N - 1][1], dp[N - 1][2]))
		return k


class Solution:

	def distinctColoring(self, N, r, g, b):
		n = N
		temp = [0, 0, 0]
		dp = []
		temp[0] = r[0]
		temp[1] = g[0]
		temp[2] = b[0]
		dp.append(temp)
		for i in range(1, N):
			temp = [0, 0, 0]
			temp[0] = r[i] + min(dp[i - 1][1], dp[i - 1][2])
			temp[1] = g[i] + min(dp[i - 1][0], dp[i - 1][2])
			temp[2] = b[i] + min(dp[i - 1][1], dp[i - 1][0])
			dp.append(temp)
		return min(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2])


class Solution:

	def distinctColoring(self, N, r, g, b):
		a = [r, g, b]
		n = N
		dp = []
		for i in range(3):
			dp.append([-1] * n)
		for i in range(3):
			dp[i][n - 1] = a[i][n - 1]
		for i in range(n - 2, -1, -1):
			for j in range(3):
				temp1 = 1000000000000000
				for k in range(3):
					if j == k:
						continue
					temp1 = min(temp1, dp[k][i + 1])
				dp[j][i] = temp1 + a[j][i]
		ans = min(dp[0][0], dp[1][0], dp[2][0])
		return ans


class Solution:

	def distinctColoring(self, N, r, g, b):
		vr = []
		vg = []
		vb = []
		for i in range(N):
			if i == 0:
				vr.append(r[0])
				vg.append(g[0])
				vb.append(b[0])
			else:
				vr.append(r[i] + min(vg[i - 1], vb[i - 1]))
				vb.append(b[i] + min(vr[i - 1], vg[i - 1]))
				vg.append(g[i] + min(vr[i - 1], vb[i - 1]))
		return min(vr[-1], vb[-1], vg[-1])


class Solution:

	def distinctColoring(self, N, r, g, b):
		x = []
		x.append(r)
		x.append(g)
		x.append(b)
		for i in range(1, len(r)):
			for j in range(3):
				if j == 0:
					x[j][i] = min(x[1][i - 1], x[2][i - 1]) + x[j][i]
				if j == 1:
					x[j][i] = min(x[0][i - 1], x[2][i - 1]) + x[j][i]
				if j == 2:
					x[j][i] = min(x[1][i - 1], x[0][i - 1]) + x[j][i]
		return min(x[0][-1], x[1][-1], x[2][-1])


class Solution:

	def distinctColoring(self, N, r, g, b):
		ans = [[0 for i in range(3)] for j in range(N)]
		ans[0][0] = r[0]
		ans[0][1] = g[0]
		ans[0][2] = b[0]
		for i in range(1, N):
			ans[i][0] = r[i] + min(ans[i - 1][1], ans[i - 1][2])
			ans[i][1] = g[i] + min(ans[i - 1][0], ans[i - 1][2])
			ans[i][2] = b[i] + min(ans[i - 1][0], ans[i - 1][1])
		return min(ans[N - 1])


class Solution:

	def distinctColoring(self, N, r, g, b):
		grid = []
		for i in range(N):
			temp = [0] * 3
			grid.append(temp)
		grid[0][0] = r[0]
		grid[0][1] = g[0]
		grid[0][2] = b[0]
		for i in range(1, N):
			grid[i][0] = min(grid[i - 1][1], grid[i - 1][2]) + r[i]
			grid[i][1] = min(grid[i - 1][0], grid[i - 1][2]) + g[i]
			grid[i][2] = min(grid[i - 1][0], grid[i - 1][1]) + b[i]
		return min(grid[N - 1])


List = list()

class Solution:

	def distinctColoring(self, n: int, r: List, g: List, b: List):
		dp = [[0] * 3 for i in range(n + 1)]
		for i in range(1, n + 1):
			dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + r[i - 1]
			dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + g[i - 1]
			dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + b[i - 1]
		return min(dp[n][0], dp[n][1], dp[n][2])


class Solution:

	def distinctColoring(self, N, r, g, b):
		(pr, pg, pb) = (0, 0, 0)
		for i in range(N):
			pcr = r[i] + min(pg, pb)
			pcg = g[i] + min(pr, pb)
			pcb = b[i] + min(pr, pg)
			(pr, pg, pb) = (pcr, pcg, pcb)
		return min(pr, pg, pb)


class Solution:

	def distinctColoring(self, N, r, g, b):
		(rc, gc, bc) = (0, 0, 0)
		for i in range(N):
			prc = r[i] + min(gc, bc)
			qgc = g[i] + min(rc, bc)
			rbc = b[i] + min(rc, gc)
			(rc, gc, bc) = (prc, qgc, rbc)
		return min(rc, gc, bc)


class Solution:

	def distinctColoring(self, N, r, g, b):
		(rc, gc, bc) = (0, 0, 0)
		for i in range(N):
			nrc = r[i] + min(gc, bc)
			ngc = g[i] + min(rc, bc)
			nbc = b[i] + min(rc, gc)
			(rc, gc, bc) = (nrc, ngc, nbc)
		return min(rc, gc, bc)


class Solution:

	def distinctColoring(self, N, r, g, b):
		red = green = blue = nred = ngreen = nblue = 0
		red = r[0]
		green = g[0]
		blue = b[0]
		for i in range(1, N):
			nred = min(green, blue) + r[i]
			ngreen = min(red, blue) + g[i]
			nblue = min(red, green) + b[i]
			red = nred
			green = ngreen
			blue = nblue
		return min(nred, green, nblue)


class Solution:

	def distinctColoring(self, N, r, g, b):
		(rr, gg, bb) = (0, 0, 0)
		for i in range(N):
			ar = r[i] + min(gg, bb)
			ag = g[i] + min(rr, bb)
			ab = b[i] + min(rr, gg)
			(rr, gg, bb) = (ar, ag, ab)
		return min(rr, gg, bb)


class Solution:

	def distinctColoring(self, N, r, g, b):
		(rc, gc, bc) = (0, 0, 0)
		for i in range(N):
			arc = r[i] + min(gc, bc)
			agc = g[i] + min(rc, bc)
			abc = b[i] + min(rc, gc)
			(rc, gc, bc) = (arc, agc, abc)
		return min(arc, agc, abc)


from heapq import heappush, heappop

class Solution:

	def distinctColoring(self, N, r, g, b):
		dp = [[0 for _ in range(3)] for _ in range(N)]
		dp[0][0] = r[0]
		dp[0][1] = g[0]
		dp[0][2] = b[0]
		for i in range(1, N):
			dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + r[i]
			dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + g[i]
			dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + b[i]
		return min(dp[N - 1][0], dp[N - 1][1], dp[N - 1][2])


class Solution:

	def distinctColoring(self, N, r, g, b):
		dp = [[0 for i in range(3)] for i in range(N + 1)]
		for i in range(N - 1, -1, -1):
			for j in range(3):
				ans1 = float('inf')
				ans2 = float('inf')
				ans3 = float('inf')
				if j != 0:
					ans1 = dp[i + 1][0] + r[i]
				if j != 1:
					ans2 = dp[i + 1][1] + g[i]
				if j != 2:
					ans3 = dp[i + 1][2] + b[i]
				dp[i][j] = min(ans1, ans2, ans3)
		return min(dp[0][0], dp[0][1], dp[0][2])


(RED, GREEN, BLUE) = (0, 1, 2)

class Solution:

	def distinctColoring(self, n, red, green, blue):
		dp = [red[0], green[0], blue[0]]
		for i in range(1, n):
			new_dp = [0] * 3
			new_dp[RED] = red[i] + min(dp[GREEN], dp[BLUE])
			new_dp[BLUE] = blue[i] + min(dp[GREEN], dp[RED])
			new_dp[GREEN] = green[i] + min(dp[BLUE], dp[RED])
			dp = new_dp
		return min(dp)


class Solution:

	def distinctColoring(self, N, r, g, b):
		dp = [[0, 0, 0] for i in range(N + 1)]
		for i in range(N - 1, -1, -1):
			for j in range(3):
				if j == 0:
					dp[i][j] = r[i] + min(dp[i + 1][1], dp[i + 1][2])
				elif j == 1:
					dp[i][j] = g[i] + min(dp[i + 1][0], dp[i + 1][2])
				else:
					dp[i][j] = b[i] + min(dp[i + 1][0], dp[i + 1][1])
		return min(dp[0])


class Solution:

	def distinctColoring(self, N, r, g, b):
		dpr = [r[0]]
		dpg = [g[0]]
		dpb = [b[0]]
		for i in range(1, N):
			dpr.append(0)
			dpg.append(0)
			dpb.append(0)
		for i in range(1, N):
			dpr[i] = min(dpg[i - 1], dpb[i - 1]) + r[i]
			dpg[i] = min(dpr[i - 1], dpb[i - 1]) + g[i]
			dpb[i] = min(dpr[i - 1], dpg[i - 1]) + b[i]
		mini = min(dpr[N - 1], dpg[N - 1], dpb[N - 1])
		return mini


class Solution:

	def distinctColoring(self, N, r, g, b):
		d = [r[0], g[0], b[0]]
		for i in range(1, N):
			c = [1000000000000.0, 1000000000000.0, 1000000000000.0]
			c[0] = min(d[1] + r[i], d[2] + r[i])
			c[1] = min(d[2] + g[i], d[0] + g[i])
			c[2] = min(d[0] + b[i], d[1] + b[i])
			d = c
		return min(d)