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