Erica is an undergraduate student at USC, and she is preparing for a very important exam. There are n days left for her to review all the lectures. To make sure she can finish all the materials, in every two consecutive days she must go through at least k lectures. For example, if k = 5 and she learned 2 lectures yesterday, then she must learn at least 3 today. Also, Ericas attention and stamina for each day is limited, so for ith day if Erica learns more than ai lectures, she will be exhausted that day.
You are asked to help her to make a plan. Design an Dynamic Programming algorithm that output the lectures she should learn each day (lets say bi), so that she can finish the lectures and being as less exhausted as possible(Specifically, minimize the sum of max(0,bi ai)). Explain your algorithm and analyze its complexity.
