Given an array A[] of positive integers. The task is to complete the function which returns an integer denoting the minimum sum subsequence from the array such that at least one value among all groups of four consecutive elements is picked.
Examples:
Input: A[] = {1, 2, 3, 4, 5, 6, 7, 8}
Output: 6
6 is sum of output subsequence {1, 5}
Following 4 length subarrays are possible
(1, 2, 3, 4), (2, 3, 4, 5), (3, 4, 5, 6),
(4, 5, 6, 7), (5, 6, 7, 8)
Here, Our subsequence {1, 5} has an element from all
above groups of four consecutive elements.
Input: A[] = {2, 1, 3} 
Output: 1 
The N (size of A) is less than 4, so the subsequnce is {1}.
Input: A[] = {1, 2, 3, 3, 4, 5, 6, 1}
Output: 4
The subsequence is {3, 1}. Here we consider
second three.
Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains two lines. The first line of each test case contains an integer N. Then in the next line are N space separated values of the array A[].
Output:
For each test case in a new line output will be the min sum of such subsequence .
Constraints:
1<=T<=100
1<=N<=50
1<=A[]<=1000
Example(To be used only for expected output):
Input:
2
8
1 2 3 4 5 6 7 8
8
1 2 3 3 4 5 6 1
Output:
6
4

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Data structures

Starter code: # Your task is to complete this function

# Function should return an integer

class Solution:

    def minSum(arr, n):

        # Code here

Solutions:
class Solution:

	def minSum(arr, n):
		if n <= 4:
			return min(arr)
		a = arr[0]
		b = arr[1]
		c = arr[2]
		d = arr[3]
		e = arr[4] + min(a, b, c, d)
		for i in range(5, n):
			a = b
			b = c
			c = d
			d = e
			e = arr[i] + min(a, b, c, d)
		a = b
		b = c
		c = d
		d = e
		return min(a, b, c, d)


class Solution:

	def minSum(arr, n):
		for i in range(4, n):
			arr[i] += min(arr[i - 4:i])
		return min(arr[-4:])


class Solution:

	def minSum(arr, n):
		if n > len(arr):
			return False
		if len(arr) < 5:
			return min(arr)
		sub_problem_store = [0] * n
		for i in range(0, 4):
			sub_problem_store[i] = arr[i]
		for i in range(4, n):
			(a, b, c, d) = sub_problem_store[i - 4:i]
			minimize_subset = arr[i] + min(a, b, c, d)
			sub_problem_store[i] = minimize_subset
		return min(sub_problem_store[-4:])


class Solution:

	def minSum(arr, n):
		min_sum = float('inf')
		if len(arr) < 5:
			for curr_num in arr:
				if curr_num < min_sum:
					min_sum = curr_num
			return min_sum
		min_sum_arr = []
		for i in range(0, len(arr)):
			if i < 4:
				min_sum_arr.append(arr[i])
			else:
				last_four_min = min(min_sum_arr[i - 1], min_sum_arr[i - 2], min_sum_arr[i - 3], min_sum_arr[i - 4])
				min_sum_arr.append(last_four_min + arr[i])
		min_sum = min(min_sum_arr[n - 4:n])
		return min_sum


class Solution:

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


import sys
INT_MAX = sys.maxsize

class Solution:

	def minSum(arr, n):
		if n <= 4:
			res = arr[0]
			for i in range(1, n):
				res = min(res, arr[i])
			return res
		a = arr[0]
		b = arr[1]
		c = arr[2]
		d = arr[3]
		e = INT_MAX
		for i in range(4, n):
			e = a + arr[i]
			e = min(e, b + arr[i])
			e = min(e, c + arr[i])
			e = min(e, d + arr[i])
			a = b
			b = c
			c = d
			d = e
		return min(a, b, c, d)


class Solution:

	def minSum(arr, n):
		if n <= 4:
			return min(arr)
		dp = [-1] * n
		dp[0] = arr[0]
		dp[1] = arr[1]
		dp[2] = arr[2]
		dp[3] = arr[3]

		def recursion(idx):
			if dp[idx] != -1:
				return dp[idx]
			calc = arr[idx] + min(recursion(idx - 1), recursion(idx - 2), recursion(idx - 3), recursion(idx - 4))
			dp[idx] = calc
			return dp[idx]
		recursion(n - 1)
		return min(dp[n - 4], dp[n - 3], dp[n - 2], dp[n - 1])


from functools import lru_cache

class Solution:

	def minSum(arr, n):
		if n < 5:
			return min(arr)

		@lru_cache(None)
		def dfs(s, i, j):
			if i == n:
				return s
			if i - j == 4:
				return dfs(s + arr[i], i + 1, i)
			return min(dfs(s + arr[i], i + 1, i), dfs(s, i + 1, j))
		return dfs(0, 0, -1)


import collections as c

class Solution:

	def minSum(arr, n):
		if len(arr) < 4:
			return min(arr)
		idx_tuple_map = {}
		total_idx_set = set()
		num_idx_map = c.defaultdict(set)
		for (idx, consec_tuple) in enumerate(zip(arr, arr[1:], arr[2:], arr[3:])):
			idx_tuple_map[idx] = consec_tuple
			total_idx_set.add(idx)
			for i in range(len(consec_tuple)):
				num_idx_map[idx + i].add(idx)
		min_sum = float('inf')

		def get_sum(curr_idx, curr_sum, curr_idx_set, dat_list):
			nonlocal min_sum
			if curr_idx_set == total_idx_set:
				if curr_sum < min_sum:
					min_sum = min(min_sum, curr_sum)
				return
			if curr_idx == len(arr):
				return
			if curr_sum > min_sum:
				return
			get_sum(curr_idx + 1, curr_sum + arr[curr_idx], curr_idx_set.union(num_idx_map[curr_idx]), dat_list + [curr_idx])
			get_sum(curr_idx + 1, curr_sum, curr_idx_set.copy(), dat_list.copy())
		get_sum(0, 0, set(), [])
		return min_sum


import sys

class Solution:

	def minSum(arr, n):
		if n <= 4:
			return min(arr)
		a1 = arr[0]
		a2 = arr[1]
		a3 = arr[2]
		a4 = arr[3]
		s = 0
		for i in range(4, n):
			s = arr[i] + min(a1, a2, a3, a4)
			a1 = a2
			a2 = a3
			a3 = a4
			a4 = s
		x = min(a1, a2, a3, a4)
		return x


class Solution:

	def minSum(arr, n):
		if n < 4:
			return min(arr)
		dp = [arr[i] for i in range(4)]
		for i in range(4, n):
			mn = min(dp)
			dp.pop(0)
			dp.append(arr[i] + mn)
		return min(dp)


class Solution:

	def minSum(arr, n):
		if n <= 4:
			return min(arr)
		dp1 = [0] * n
		dp2 = [0] * n

		def get(vec, idx):
			if 0 <= idx < n:
				return vec[idx]
			return 0
		for i in range(n):
			dp1[i] = arr[i] + min(get(dp1, i - 1), get(dp1, i - 2), get(dp1, i - 3), get(dp1, i - 4))
		for i in range(n - 1, -1, -1):
			dp2[i] = arr[i] + min(get(dp2, i + 1), get(dp2, i + 2), get(dp2, i + 3), get(dp2, i + 4))
		return min(min(dp1[-4:]), min(dp2[:4]))


class Solution:

	def minSum(arr, n):
		if n <= 4:
			return min(arr)
		dp = [arr[i] for i in range(n)]
		for i in range(4, n):
			dp[i] = arr[i] + min(dp[i - 4:i])
		ans = min(dp[n - 4:n])
		return ans
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution
		print(ob.minSum(arr, n))


class Solution:

	def minSum(arr, n):
		if n <= 4:
			return min(arr)
		a = arr[0]
		b = arr[1]
		c = arr[2]
		d = arr[3]
		for i in range(4, n):
			e = arr[i] + min([a, b, c, d])
			a = b
			b = c
			c = d
			d = e
		return min([a, b, c, d])
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution
		print(ob.minSum(arr, n))


class Solution:

	def minSum(arr, n):
		dp = [0] * n
		if n <= 4:
			return min(arr)
		for i in range(4):
			dp[n - i - 1] = arr[n - i - 1]
		for i in range(n - 5, -1, -1):
			dp[i] = arr[i] + min(dp[i + 1], dp[i + 2], dp[i + 3], dp[i + 4])
		return min(dp[0], dp[1], dp[2], dp[3])
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution
		print(ob.minSum(arr, n))


import math

class Solution:

	def minSum(A, n):
		if n <= 4:
			return min(A)
		else:
			l = n - 3
			dp = [math.inf] * l
			for i in range(n - 1, n - 1 - 4, -1):
				dp[l - 1] = min(dp[l - 1], A[i])
			for i in range(l - 2, -1, -1):
				res = math.inf
				for j in range(0, 4):
					if i + j + 1 < l:
						res = min(res, A[i + j] + dp[i + j + 1])
					else:
						res = min(res, A[i + j])
				dp[i] = res
		return res
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution
		print(ob.minSum(arr, n))


class Solution:

	def minSum(arr, n):
		if len(arr) <= 4:
			return min(arr)
		sum = [0 for i in range(n)]
		sum[0] = arr[0]
		sum[1] = arr[1]
		sum[2] = arr[2]
		sum[3] = arr[3]
		for i in range(4, n):
			sum[i] = arr[i] + min(sum[i - 4:i])
		return min(sum[-4:])


class Solution:

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


class Solution:

	def minSum(arr, n):
		if n <= 4:
			return min(arr)
		(a, b, c, d) = arr[:4]
		for i in range(4, n):
			e = arr[i] + min(a, b, c, d)
			(a, b, c, d) = (b, c, d, e)
		return min(a, b, c, d, e)


class Solution:

	def minSum(arr, n):
		if n <= 4:
			return min(arr)
		dp = [0] * n
		dp[0:4] = arr[0:4]
		for i in range(4, n):
			dp[i] = arr[i] + min(dp[i - 4:i])
		return min(dp[n - 4:n])


class Solution:

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


class Solution:

	def minSum(arr, n):
		if n <= 4:
			x = arr[0]
			for i in range(1, n):
				if arr[i] < x:
					x = arr[i]
			return x
		dp = [arr[0], arr[1], arr[2], arr[3]]
		for i in range(4, n):
			e = arr[i] + min(dp[i - 1], dp[i - 2], dp[i - 3], dp[i - 4])
			dp.append(e)
		return min(dp[n - 1], dp[n - 2], dp[n - 3], dp[n - 4])


class Solution:

	def minSum(arr, n):
		if len(arr) <= 4:
			return min(arr)
		else:
			dp = [arr[i] for i in range(n)]
			for i in range(4, n):
				dp[i] = arr[i] + min(dp[i - 4:i])
		return min(dp[n - 4:n])