Given an array A consisting of N non-negative integers your task is to find the minimum sum of the array such that out of 3 consecutive  elements you need to add at-least one.
 
Example 1:
Input:
N = 6
A[] = {1, 2, 3, 6, 7, 1}
Output:
4
Explanation:
Moving from left to right 3+1. When 3
is added next 3 consecutive elements
be 6, 7 and 1, from which we take 1.
Which covers all subarray of lenght 3
(3+1=4).
 
Example 2:
Input:
2
3 2
Output:
0
Explanation:
We won't take any element as the
array length is less than 3.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minSum() which takes the array A[] and its size N as inputs and returns the minimum sum that can be obtained.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ a[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Starter code: #User function Template for python3

class Solution:
    def minSum(self, a, n):
        # Write your code here

Solutions:
import sys
import numpy as np

class Solution:

	def rec_sol(self, a, n):
		if n <= 2:
			return 0
		return min(min(a[n - 1] + self.rec_sol(a, n - 1), a[n - 2] + self.rec_sol(a, n - 2)), a[n - 3] + self.rec_sol(a, n - 3))

	def mem_sol(self, a, n, dp):
		if n <= 2:
			return 0
		if dp[n] != -1:
			return dp[n]
		dp[n] = min(min(a[n - 1] + self.mem_sol(a, n - 1, dp), a[n - 2] + self.mem_sol(a, n - 2, dp)), a[n - 3] + self.mem_sol(a, n - 3, dp))
		return dp[n]

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

	def minSum(self, a, n):
		return self.dp_sol(a, n)


class Solution:

	def minSum(self, a, n):
		if n < 3:
			return 0
		d = [a[0], a[1], a[2]]
		for i in range(3, n):
			d.append(min(a[i] + d[len(d) - 1], a[i] + d[len(d) - 2], a[i] + d[len(d) - 3]))
		return min(d[len(d) - 1], d[len(d) - 2], d[len(d) - 3])


class Solution:

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


def minimum(a, b, c):
	return min(min(a, b), c)

class Solution:

	def minSum(self, a, n):
		if n < 3:
			return 0
		sum = []
		sum.append(a[0])
		sum.append(a[1])
		sum.append(a[2])
		for i in range(3, n):
			sum.append(a[i] + minimum(sum[i - 3], sum[i - 2], sum[i - 1]))
		return minimum(sum[n - 1], sum[n - 2], sum[n - 3])