Answer Happy

5. Given an array A[1..n] - our task is to select a subsequence of this array. The sum of the numbers selected for this subsequence is to be minimized. The constraint is that any number which is not selected must have at least one of its neighbor selected. Give a dynamic programming algorithm for this task. You will need to set up subproblems, define metric(s) to compute for each subproblem and then write recurrences for how to compute. Here are some example for helping with your understanding. If A = 1,5, 3, 7, 6, 4, 1, 2 then the best subse- quence you can choose is 1,3,4,1. This has cost 9. If the subsequnce you choose is 1,3, 1, 2 that will be lesser cost but it is invalid because there is no one covering 6. On the othe hand 5,6,1 is valid but has higher cost.