I got this problem as an interview questions and I was blank all the way, I thought it was pressure but as I try to do it now I am still blank, anyway to solve this problem, I am blank so a solution would be more helpful than just explaining it as I am just trying to move on from this problem and do something else, more of like a review question that i can look at for the next interview prep. Thanks in advance.
Assume that you have a list of n home maintenance/repair tasks (numbered from 1 to n) that must be done in list order on your house. You can either do each task i yourself at a positive cost (that includes your time and effort) of c[i]. Alternatively, you could hire a handyman who will do the next 4 tasks on your list for the fixed cost h (regardless of how much time and effort those 4 tasks would cost you). You are to create a dynamic programming algorithm that finds a minimum cost way of completing the tasks. The inputs to the problem are h and the array of costs c, . . . , c[n].
Here is an example. [1,3,5,6,7,2,1,3,1000] is the cost array by yourself. The handyman cost is 11. For any sequence greater than or equal to 4 tasks we would add handyman to do the tasks. In this case we would add handyman for 1...4, and 5....8, hence the total cost here is 23, and it is the minimum. Note that the handyman can not do less than 4 consecutive tasks.
Here are the subproblems I was given to solve:
find and justify a recurrence (with boundary conditions) giving the optimal cost for completing the tasks
O(n)-time recursive algorithm with memoization for calculating the value of the recurrence and a bottom up algorithm