REL104 - Editorial

PROBLEM LINK:

Practice 
Contest

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.

//