There is a row of N walls in Geeksland. The king of Geeksland ordered Alexa to color all the walls on the occasion of New Year. Alexa can color each wall with either pink, black, or yellow. The cost associated with coloring each wall with a particular color is represented by a 2D array colors of size N*3 , where colors[i][0], colors[i][1], and colors[i][2] is the cost of painting ith wall with colors pink, black, and yellow respectively.
You need to find the minimum cost to color all the walls such that no two adjacent walls have the same color.
Example 1:
Input:
N = 3
colors[][] = {{14, 2, 11},
             {11, 14, 5},
             {14, 3, 10}}
Output:
10
Explanation:
Color wall 0 with black. Cost = 2. 
Color wall 1 with yellow. Cost = 5. 
Color wall 2 with black. Cost = 3.
Total Cost = 2 + 5 + 3 = 10
Example 2:
Input:
N = 2
colors[][] = {{1, 2, 3},
             {1, 4, 6}}
Output:
3
Explanation:
Color wall 0 with black. Cost = 2
Color wall 1 with pink. Cost = 1
Total Cost = 1 + 2 = 3
Your Task:
Your task is to complete the function minCost() which takes the 2D integer array colors and an integer N as the input parameters and returns an integer, representing the minimum cost to color all the walls.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
	1 <= N <= 10^{5}
	1 <= colors[i][0], colors[i][1], colors[i][2] <= 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution():

    def minCost(self, colors, N):

        #your code goes here

Solutions:
class Solution:

	def minCost(self, colors, N):
		(pink, black, yellow) = (0, 0, 0)
		for (p, b, y) in colors:
			(pink, black, yellow) = (p + min(black, yellow), b + min(pink, yellow), y + min(pink, black))
		return min(pink, black, yellow)


from copy import deepcopy

class Solution:

	def minCost(self, colors, N):
		self.n = N
		self.colors = colors
		row = [0] * 3
		self.dp = [deepcopy(row) for i in range(N + 1)]
		for i in range(self.n, -1, -1):
			for prev in range(3):
				if i == self.n:
					self.dp[i][prev] = 0
				else:
					Min = float('inf')
					for j in range(3):
						if j != prev:
							Min = min(Min, self.colors[i][j] + self.dp[i + 1][j])
					self.dp[i][prev] = Min
		return min(self.dp[0])

	def find(self, i, prev):
		if i == self.n:
			return 0
		Min = float('inf')
		for j in range(3):
			if j != prev:
				Min = min(Min, self.colors[i][j] + self.find(i + 1, j))
		return Min


class Solution:

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


import sys
sys.setrecursionlimit(1000000)
from functools import lru_cache
from enum import Enum

class Color(Enum):
	PINK = 0
	BLACK = 1
	YELLOW = 2

class Solution:

	@lru_cache()
	def find_color(self, current_color, index):
		if index == len(self.colors):
			return 0
		if current_color is Color.PINK:
			return self.colors[index][Color.PINK.value] + min(self.find_color(Color.BLACK, index + 1), self.find_color(Color.YELLOW, index + 1))
		elif current_color is Color.BLACK:
			return self.colors[index][Color.BLACK.value] + min(self.find_color(Color.PINK, index + 1), self.find_color(Color.YELLOW, index + 1))
		else:
			return self.colors[index][Color.YELLOW.value] + min(self.find_color(Color.PINK, index + 1), self.find_color(Color.BLACK, index + 1))

	def minCost(self, colors, N):
		self.colors = colors
		return min(self.find_color(Color.PINK, 0), self.find_color(Color.BLACK, 0), self.find_color(Color.YELLOW, 0))


import sys
sys.setrecursionlimit(1000000)
from functools import lru_cache
from enum import Enum

class Color(Enum):
	PINK = 0
	BLACK = 1
	YELLOW = 2

class Solution:

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


class Solution:

	def minCost(self, color, N):
		for i in range(1, N):
			color[i][0] += min(color[i - 1][1], color[i - 1][2])
			color[i][1] += min(color[i - 1][2], color[i - 1][0])
			color[i][2] += min(color[i - 1][1], color[i - 1][0])
		return min(color[-1])


class Solution:

	def minCost(self, colors, N):
		dp = colors[0]
		for i in range(1, N):
			dp1 = colors[i][0] + min(dp[1], dp[2])
			dp2 = colors[i][1] + min(dp[0], dp[2])
			dp3 = colors[i][2] + min(dp[0], dp[1])
			dp = [dp1, dp2, dp3]
		return min(dp)


class Solution:

	def minCost(self, colors, N):
		dp = [[0 for _ in range(len(colors[0]))] for _ in range(N)]
		dp[0] = colors[0]
		for i in range(1, N):
			for j in range(len(colors[0])):
				dp[i][j] = min([y for (x, y) in enumerate(dp[i - 1]) if x != j]) + colors[i][j]
		return min(dp[-1])


class Solution:

	def minCost(self, colors, N):
		p = b = y = 0
		for i in range(N):
			cp = min(b, y) + colors[i][0]
			cb = min(p, y) + colors[i][1]
			cy = min(p, b) + colors[i][2]
			(p, b, y) = (cp, cb, cy)
		return min(p, min(b, y))


class Solution:

	def minCost(self, arr, n):
		dp = [[10000000000000.0 for i in range(3)] for j in range(n + 1)]
		for i in range(3):
			dp[0][i] = arr[0][i]
		for i in range(1, n):
			for j in range(3):
				temp = 10000000000000.0
				for k in range(3):
					if j == k:
						continue
					temp = min(temp, dp[i - 1][k])
				dp[i][j] = temp + arr[i][j]
		return min(dp[n - 1])


class Solution:

	def minCost(self, c, N):
		dp = c
		n = len(c)
		for i in range(1, len(c)):
			dp[i][0] += min(dp[i - 1][1], dp[i - 1][2])
			dp[i][1] += min(dp[i - 1][0], dp[i - 1][2])
			dp[i][2] += min(dp[i - 1][0], dp[i - 1][1])
		return min({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]})


class Solution:

	def minCost(self, c, N):
		for i in range(N - 2, -1, -1):
			for j in range(3):
				c[i][j] += min(c[i + 1][(j + 1) % 3], c[i + 1][(j + 2) % 3])
		return min(c[0])


inf = 10 ** 18

class Solution:

	def minCost(self, colors, N):
		ans = colors[0][:]
		for i in range(1, n):
			tmp = ans[:]
			ans = [inf, inf, inf]
			for j in range(3):
				ans[j] = min(ans[j], tmp[(j + 1) % 3] + colors[i][j])
				ans[j] = min(ans[j], tmp[(j + 2) % 3] + colors[i][j])
		return min(ans)


class Solution:

	def minCost(self, colors, N):
		a = b = c = 0
		for i in range(N - 1, -1, -1):
			p = colors[i][0] + min(b, c)
			q = colors[i][1] + min(a, c)
			r = colors[i][2] + min(a, b)
			(a, b, c) = (p, q, r)
		return min(a, b, c)


class Solution:

	def get(self, ch, lt):
		if ch == 0:
			if lt[1] > lt[2]:
				return [2, lt[2]]
			return [1, lt[1]]
		if ch == 1:
			if lt[0] > lt[2]:
				return [2, lt[2]]
			return [0, lt[0]]
		if ch == 2:
			if lt[0] > lt[1]:
				return [1, lt[1]]
			return [0, lt[0]]

	def minCost(self, colors, N):
		(pink, black, yellow) = (0, 0, 0)
		for i in range(0, N):
			c_pink = colors[i][0] + min(black, yellow)
			c_black = colors[i][1] + min(yellow, pink)
			c_yellow = colors[i][2] + min(pink, black)
			(pink, black, yellow) = (c_pink, c_black, c_yellow)
		return min(pink, black, yellow)


class Solution:

	def minCost(self, costs, N):
		if N == 0:
			return 0
		dp = [[0 for i in range(3)] for j in range(N)]
		dp[0][0] = costs[0][0]
		dp[0][1] = costs[0][1]
		dp[0][2] = costs[0][2]
		for i in range(1, N, 1):
			dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0]
			dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1]
			dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2]
		return min(dp[N - 1][0], min(dp[N - 1][1], dp[N - 1][2]))


class Solution:

	def minCost(self, colors, N):
		dp = [[0] * 3 for i in range(N)]
		for j in range(3):
			dp[0][j] = colors[0][j]
		for i in range(1, N):
			for j in range(3):
				dp[i][j] = colors[i][j] + min((dp[i - 1][k] for k in range(3) if k != j))
		return min(dp[N - 1])


import sys
sys.setrecursionlimit(10 ** 7)

class Solution:

	def prev(self, wall, prev, row, d):
		if row == len(wall):
			return 0
		if d.get((prev, row)) != None:
			return d[prev, row]
		if prev == 0:
			d[prev, row] = min(wall[row][1] + self.prev(wall, 1, row + 1, d), wall[row][2] + self.prev(wall, 2, row + 1, d))
			return d[prev, row]
		if prev == 1:
			d[prev, row] = min(wall[row][0] + self.prev(wall, 0, row + 1, d), wall[row][2] + self.prev(wall, 2, row + 1, d))
			return d[prev, row]
		if prev == 2:
			d[prev, row] = min(wall[row][1] + self.prev(wall, 1, row + 1, d), wall[row][0] + self.prev(wall, 0, row + 1, d))
			return d[prev, row]
		d[prev, row] = min(wall[row][1] + self.prev(wall, 1, row + 1, d), wall[row][2] + self.prev(wall, 2, row + 1, d), wall[row][0] + self.prev(wall, 0, row + 1, d))
		return d[prev, row]

	def minCost(self, colors, N):
		d = dict()
		return self.prev(colors, -1, 0, d)


class Solution:

	def minCost(self, colors, N):
		pink = 0
		black = 0
		yellow = 0
		cur_p = 0
		cur_b = 0
		cur_y = 0
		for i in range(N):
			cur_p = min(black, yellow) + colors[i][0]
			cur_b = min(pink, yellow) + colors[i][1]
			cur_y = min(pink, black) + colors[i][2]
			pink = cur_p
			black = cur_b
			yellow = cur_y
		return min(pink, min(black, yellow))


class Solution:

	def minCost(self, colors, N):
		cost = [[] for i in range(N)]
		cost[0].append(colors[0][0])
		cost[0].append(colors[0][1])
		cost[0].append(colors[0][2])
		for i in range(1, N):
			cost[i].append(colors[i][0] + min(cost[i - 1][1], cost[i - 1][2]))
			cost[i].append(colors[i][1] + min(cost[i - 1][0], cost[i - 1][2]))
			cost[i].append(colors[i][2] + min(cost[i - 1][0], cost[i - 1][1]))
		return min(cost[N - 1][0], cost[N - 1][1], cost[N - 1][2])


class Solution:

	def minCost(self, colors, N):
		(c1, c2, c3) = (colors[0][0], colors[0][1], colors[0][2])
		for x in range(1, N):
			(c1, c2, c3) = (colors[x][0] + min(c2, c3), colors[x][1] + min(c1, c3), colors[x][-1] + min(c2, c1))
		return min(c1, c2, c3)


class Solution:

	def minCost(self, colors, N):
		table = [[colors[0][0], colors[0][1], colors[0][2]]]
		for i in range(1, N):
			pink_cost = colors[i][0] + min(table[i - 1][1], table[i - 1][2])
			black_cost = colors[i][1] + min(table[i - 1][0], table[i - 1][2])
			yellow_cost = colors[i][2] + min(table[i - 1][0], table[i - 1][1])
			table.append([pink_cost, black_cost, yellow_cost])
		return min(table[-1])


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:
	arr = []
	res = float('inf')

	def fun(self, colors, ind, n, cost, color):
		if ind == n:
			return 0
		if self.arr[ind][color] != -1:
			return self.arr[ind][color]
		opt1 = float('inf')
		opt2 = float('inf')
		opt3 = float('inf')
		if color != 0:
			opt1 = self.fun(colors, ind + 1, n, cost + colors[ind][color], 0)
		if color != 1:
			opt2 = self.fun(colors, ind + 1, n, cost + colors[ind][color], 1)
		if color != 2:
			opt3 = self.fun(colors, ind + 1, n, cost + colors[ind][color], 2)
		self.arr[ind][color] = min(opt1, opt2, opt3) + colors[ind][color]
		return self.arr[ind][color]

	def minCost(self, colors, N):
		self.arr = [[-1, -1, -1] for _ in range(N)]
		self.fun(colors, 0, N, 0, 0)
		self.fun(colors, 0, N, 0, 1)
		self.fun(colors, 0, N, 0, 2)
		return min(self.arr[0])


class Solution:

	def minCost(self, colors, N):
		pink = 0
		black = 0
		yellow = 0
		for i in range(N):
			curr_pink = min(black, yellow) + colors[i][0]
			curr_black = min(pink, yellow) + colors[i][1]
			curr_yellow = min(black, pink) + colors[i][2]
			pink = curr_pink
			black = curr_black
			yellow = curr_yellow
		return min(pink, min(black, yellow))


class Solution:

	def minCost(self, colors, N):
		dp = [[0] * 3 for _ in range(N)]
		for i in range(N):
			for j in range(3):
				if i == 0:
					dp[i][j] = colors[i][j]
				elif j == 1:
					dp[i][j] = colors[i][j] + min(dp[i - 1][0], dp[i - 1][2])
				elif j == 2:
					dp[i][j] = colors[i][j] + min(dp[i - 1][1], dp[i - 1][0])
				else:
					dp[i][j] = colors[i][j] + min(dp[i - 1][1], dp[i - 1][2])
		return min(dp[-1])


import sys
sys.setrecursionlimit(10 ** 6)
from functools import lru_cache

class Solution:

	def minCost(self, colors, N):

		@lru_cache(None)
		def helper(indx, flag):
			if indx >= N:
				return 0
			ans = 100000000000000
			for i in range(3):
				if 1 << i != flag:
					ans = min(ans, colors[indx][i] + helper(indx + 1, 1 << i))
			return ans
		return helper(0, 0)


import math

class Solution:

	def minCost(self, colors, N):
		dp = [[0 for j in range(N)] for i in range(3)]
		dp[0][0] = colors[0][0]
		dp[1][0] = colors[0][1]
		dp[2][0] = colors[0][2]
		for i in range(1, n):
			dp[0][i] = min(dp[1][i - 1], dp[2][i - 1]) + colors[i][0]
			dp[1][i] = min(dp[0][i - 1], dp[2][i - 1]) + colors[i][1]
			dp[2][i] = min(dp[1][i - 1], dp[0][i - 1]) + colors[i][2]
		res = min(dp[0][N - 1], dp[1][N - 1], dp[2][N - 1])
		return res


import math

class Solution:

	def minCost(self, colors, n):
		costs = colors[0]
		for i in range(1, n):
			new_costs = [math.inf] * 3
			for color in range(3):
				for other_color in range(3):
					if color != other_color:
						new_costs[color] = min(new_costs[color], costs[other_color] + colors[i][color])
			costs = new_costs
		return min(costs)


class Solution:

	def minCost(self, colors, N):
		(a, b, c) = (colors[0][0], colors[0][1], colors[0][2])
		for i in range(1, n):
			(a, b, c) = (colors[i][0] + min(b, c), colors[i][1] + min(a, c), colors[i][2] + min(a, b))
		return min(a, b, c)


class Solution:

	def minCost(self, colors, N):
		a = b = c = 0
		for i in range(len(colors)):
			pink = colors[i][0] + min(b, c)
			black = colors[i][1] + min(a, c)
			yellow = colors[i][2] + min(a, b)
			a = pink
			b = black
			c = yellow
		return min(a, b, c)


class Solution:

	def minCost(self, colors, N):
		(p, b, y) = (colors[0][0], colors[0][1], colors[0][2])
		for i in range(1, n):
			(p, b, y) = (colors[i][0] + min(b, y), colors[i][1] + min(p, y), colors[i][2] + min(p, b))
		return min(p, b, y)


class Solution:

	def minCost(self, colors, N):
		if N == 0:
			return 0
		for i in range(1, N):
			colors[i][0] = colors[i][0] + min(colors[i - 1][1], colors[i - 1][2])
			colors[i][1] = colors[i][1] + min(colors[i - 1][0], colors[i - 1][2])
			colors[i][2] = colors[i][2] + min(colors[i - 1][0], colors[i - 1][1])
		return min(colors[N - 1][0], min(colors[N - 1][1], colors[N - 1][2]))


class Solution:

	def minCost(self, colors, N):
		cost = [[], [], []]
		for i in range(N):
			if i == 0:
				for j in range(3):
					cost[j].append(colors[0][j])
			else:
				cost[0].append(min(cost[1][i - 1], cost[2][i - 1]) + colors[i][0])
				cost[1].append(min(cost[0][i - 1], cost[2][i - 1]) + colors[i][1])
				cost[2].append(min(cost[1][i - 1], cost[0][i - 1]) + colors[i][2])
		return min(cost[0][-1], cost[1][-1], cost[2][-1])


class Solution:

	def minCost(self, colors, N):
		x = 0
		y = 0
		z = 0
		for i in range(len(colors)):
			p = colors[i][0] + min(y, z)
			b = colors[i][1] + min(x, z)
			y = colors[i][2] + min(x, y)
			(x, y, z) = (p, b, y)
		return min(x, y, z)


class Solution:

	def minCost(self, co, n):
		a = co[0][0]
		b = co[0][1]
		c = co[0][2]
		for i in range(1, n):
			t1 = co[i][0] + min(b, c)
			t2 = co[i][1] + min(a, c)
			t3 = co[i][2] + min(a, b)
			a = t1
			b = t2
			c = t3
		return min(a, b, c)


class Solution:

	def minCost(self, colors, N):
		for i in range(1, N):
			for j in range(3):
				colors[i][j] += min(colors[i - 1][j - 1], colors[i - 1][j - 2])
		return min(colors[-1])


class Solution:

	def minCost(self, colors, N):
		(p, b, y) = (0, 0, 0)
		for (i, j, k) in colors:
			cp = min(b, y) + i
			cb = min(p, y) + j
			cy = min(p, b) + k
			(p, b, y) = (cp, cb, cy)
		return min(p, b, y)


class Solution:

	def minCost(self, colors, N):
		dp = [0, 0, 0]
		for i in colors:
			new = [0, 0, 0]
			new[0] = min(dp[1], dp[2]) + i[0]
			new[1] = min(dp[0], dp[2]) + i[1]
			new[2] = min(dp[0], dp[1]) + i[2]
			dp = new
		return min(dp)