Geek wants to inspect the quality of vegetables at each shop in the vegetable market. There are N different vegetable sellers in a line. A single kilogram each of brinjal, carrot and tomato are available with every seller but at different prices. Geek wants to buy exactly one vegetable from one shop and avoid buying the same vegetables from adjacent shops. 
Given the cost of each vegetable in each shop in a Nx3 matrix, calculate the minimum amount of money that Geek must spend in the inspection. 
Example 1:
Input: 
N = 3
cost = {{1, 50, 50}, 
        {50, 50, 50}, 
        {1, 50, 50}}
Output: 52
Explaination: 
Shop 1: Buy Brinjals for Rs 1.
Shop 2: Buy Carrot or Tomatoes for Rs 50.
Shop 3: Buy Brinjals for Rs 1.
Total = 1+50+1 = 52
Your Task:
You do not need to read input or print anything. Your task is to complete the function minCost() which takes N and Nx3 matrix cost[][] as input parameters and returns he minimum amount of money that Geek must spend in the inspection. 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5 }
1 ≤ cost[i][j] ≤ 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def minCost(self, N, cost):

        # code here

Solutions:
class Solution:

	def minCost(self, N, cost):
		for i in range(1, len(cost)):
			for j in range(len(cost[0])):
				curr_min = float('inf')
				for k in range(3):
					if j != k:
						curr_min = min(curr_min, cost[i - 1][k])
				cost[i][j] += curr_min
		ans = float('inf')
		for i in range(3):
			ans = min(ans, cost[-1][i])
		return ans


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def minCost(self, N, cost):
		dp = cost[0]
		for i in range(1, N):
			dp0 = cost[i][0] + min(dp[1], dp[2])
			dp1 = cost[i][1] + min(dp[0], dp[2])
			dp2 = cost[i][2] + min(dp[0], dp[1])
			dp = [dp0, dp1, dp2]
		return min(dp)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		cost = [[0] * 3 for x in range(N)]
		for i in range(N):
			a = input().split()
			for j in range(3):
				cost[i][j] = int(a[j])
		ob = Solution()
		print(ob.minCost(N, cost))


class Solution:

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


class Solution:

	def minCost(self, N, cost):
		min_cost = [cost[0][0], cost[0][1], cost[0][2]]
		for i in range(1, N):
			brinjal = min(min_cost[1], min_cost[2]) + cost[i][0]
			carrot = min(min_cost[0], min_cost[2]) + cost[i][1]
			tomato = min(min_cost[0], min_cost[1]) + cost[i][2]
			min_cost = [brinjal, carrot, tomato]
		return min(min_cost)


class Solution:

	def minCost(self, N, cost):
		dp = [[float('inf') for _ in range(3)] for _ in range(N)]
		dp[0] = cost[0]
		for i in range(1, N):
			for j in range(3):
				dp[i][j] = min(dp[i - 1][(j - 1) % 3], dp[i - 1][(j + 1) % 3]) + cost[i][j]
		return min(dp[N - 1])


INT_MAX = 100000000

class Solution:

	def minCost(self, N, cost):
		default_total = [INT_MAX for _ in range(9)]
		total = default_total[:]
		min_cost = INT_MAX
		shop = 2
		for (prev_veg, current_veg) in [(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]:
			total[prev_veg * 3 + current_veg] = cost[0][prev_veg] + cost[1][current_veg]
		while shop <= N - 1:
			new_total = default_total[:]
			for (prev_veg, current_veg, next_veg) in [(0, 1, 0), (0, 2, 0), (1, 0, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0), (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 1), (2, 0, 2), (2, 1, 2)]:
				index = current_veg * 3 + next_veg
				new_total[index] = min(new_total[index], total[prev_veg * 3 + current_veg] + cost[shop][next_veg])
			total = new_total[:]
			shop += 1
		min_cost = min(total)
		return min_cost


class Solution:

	def minCost(self, N, sellers):
		dp = [[0] * 3 for _ in range(len(sellers) + 1)]
		for i in range(len(sellers) - 1, 0, -1):
			for chosen in range(3):
				cost = []
				for k in range(3):
					if k == chosen:
						continue
					cost.append(sellers[i][k] + dp[i + 1][k])
				dp[i][chosen] = min(cost)
		for i in range(3):
			dp[0][i] = sellers[0][i] + dp[1][i]
		return min(dp[0])