Thursday, September 29, 2016

Find minimum sum such that one of every three consecutive elements is taken - GeeksforGeeks

Find minimum sum such that one of every three consecutive elements is taken - GeeksforGeeks
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 3 consecutive elements in the array.

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) and sum(n-3) [We must pick at least one of the last three elements].
We can recursively compute sum(i) as sum of arr[i] and minimum(sum(i-1), sum(i-2), sum(i-3)). Since there are overlapping subproblems in recursive structure of problem, we can use Dynamic Programming to solve this problem.
`// Returns minimum possible sum of elements such`
`// that an element out of every three consecutive`
`// elements is picked.`
`int` `findMinSum(``int` `arr[], ``int` `n)`
`{`
`    ``// Create a DP table to store results of`
`    ``// subpriblems. sum[i] is going to store`
`    ``// minimum possible sum when arr[i] is`
`    ``// part of the solution.`
`    ``int` `sum[n];`

`    ``// When there are less than or equal to`
`    ``// 3 elements`
`    ``sum[0] = arr[0];`
`    ``sum[1] = arr[1];`
`    ``sum[2] = arr[2];`

`    ``// Iterate through all other elements`
`    ``for` `(``int` `i=3; i<n; i++)`
`      ``sum[i] = arr[i] +`
`              ``minimum(sum[i-3], sum[i-2], sum[i-1]);`

`    ``return` `minimum(sum[n-1], sum[n-2], sum[n-3]);`
`}`

Read full article from Find minimum sum such that one of every three consecutive elements is taken - GeeksforGeeks