### PROBLEM LINK:

**Author:** Divyesh Savaliya

**Editorialist:** Divyesh Savaliya

### DIFFICULTY:

Medium - Hard

### PREREQUISITES:

Dynamic Programming

### PROBLEM:

Given an array of n non-negative numbers, the task is to find the minimum sum of elements (picked from the array) such that at least one element is picked out of every 4 consecutive elements in the array.

### EXPLANATION:

Let sum(i) be the minimum possible sum when arr[i] is part of a solution sum (not necessarily result) and is last picked element. Then our result is minimum of sum(n-1), sum(n-2), sum(n-3) and sum(n-4) [We must pick at least one of the last four elements].

We can recursively compute sum(i) as sum of arr[i] and minimum (sum(i-1), sum(i-2), sum(i-3), sum(i-4)). Since there are overlapping subproblems in recursive structure of problem, we can use Dynamic Programming to solve this problem.

Time complexity is O(N).

### AUTHOR’S SOLUTIONS:

Author’s solution can be found here.