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.