Given a matrix M of size n * n, the task is to find sum of the zigzag sequence with the largest sum. A zigzag sequence starts from the top and ends at the bottom. Two consecutive elements of sequence cannot belong to same column.
Example 1:
Input: n = 3
M = {{3, 1, 2}, 
     {4, 8, 5}, 
     {6, 9, 7}}
Output: 18
Explaination: The sequence is (3, 8, 7).
Example 2:
Input: n = 3
M = {{1, 2, 4}, 
     {3, 9, 6}, 
     {11, 3, 15}}
Output: 28
Explaination: The sequence is 4, 9, 15.
Your Task:
You do not need to read input or print anything. Your task is to complete the function zigzagSequence() which takes n and M as input parameters and returns the highest zigzag sum.
Expected Time Complexity: O(n^{3})
Expected Auxiliary Space: O(n^{2})  
Constraints:
1 ≤ n ≤ 100
1 ≤ M[i][j] ≤ 1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def zigzagSequence(self, n, M):

        # code here

Solutions:
class Solution:

	def zigzagSequence(self, n, M):
		m = n
		dp = [[0] * m for i in range(n)]
		for i in range(n):
			for j in range(m):
				if i == 0:
					dp[i][j] = M[i][j]
				else:
					for k in range(m):
						if k != j:
							dp[i][j] = max(dp[i][j], dp[i - 1][k] + M[i][j])
		return max(dp[n - 1])


class Solution:

	def zigzagSequence(self, n, M):
		dp = {}

		def dfs(i, prevCol):
			if (i, prevCol) in dp:
				return dp[i, prevCol]
			if i == 0:
				maxi = 0
				for j in range(n):
					if j != prevCol:
						maxi = max(maxi, M[i][j])
				dp[i, prevCol] = maxi
				return dp[i, prevCol]
			maxi = 0
			for j in range(n):
				if j != prevCol:
					maxi = max(maxi, M[i][j] + dfs(i - 1, j))
			dp[i, prevCol] = maxi
			return maxi
		return dfs(n - 1, n)


class Solution:

	def zigzagSequence(self, n, M):
		if n == 1:
			return M[0][0]
		for i in range(1, n):
			M[i][0] += max(M[i - 1][1:])
			M[i][-1] += max(M[i - 1][:-1])
			for j in range(1, n - 1):
				M[i][j] += max(M[i - 1][:j] + M[i - 1][j + 1:])
		return max(M[-1])


from collections import defaultdict

class Solution:

	def zigzagSequence(self, n, M):
		temp = 0
		for i in range(n):
			for j in range(n):
				M[i][j] = int(a[temp])
				temp += 1

		def yo(i, j):
			if i == n:
				return 0
			elif dp[i][j]:
				return dp[i][j]
			else:
				temp = 0
				for x in range(n):
					if x != j:
						temp = max(temp, yo(i + 1, x))
				dp[i][j] = temp + M[i][j]
				return dp[i][j]
		ma = 0
		dp = [[0] * n for i in range(n)]
		for i in range(n):
			ma = max(ma, yo(0, i))
		return ma