How to create a dynamic programming solution to this zco problem?
After much efforts i was luckily able to solve the ipl problem but have got stuck on this problem. This looks similar to the ipl problem.
Any help will be highly encouraged.

The answer:

Work[0..N] time for each workload 
Best[j,0] means he does not work on day j
Best[j,1] means he does work on day j,not j+1
Best[j,2] means he does work on day j,j+1,not j+2

Initialize :
Best[N,0] = sum(Work[i],for all i from 0 to N-1)
Best[N,1] = sum(Work[i],for all i from 0 to N-1)-Work[N-1]
Best[N,2] = sum(Work[i],for all i from 0 to N-1)

For j=N-1 to 0  j--
Best[j,0] = min(Best[j+1,0],Best[j+1,1],Best[j+1,2])
Best[j,1] = Work[j] - Best[j+1,0]
Best[j,2] = Work[j] - Best[j+1,1]

Make a table on a paper and you’ll get it.

Well why would you use DP???

Isn’t the greedy method good here???

If you solved IPL problem then just subtract your answer from total sum of array and you will get answer of SUPW problem. Check it out!!

man simple speaking was unable to understand anything there… it was all messed up.
Could u tell me the logic! I’ll try to create the dp solution my self :smiley:

Nope. That gives the wrong answer majority of the times.

1 Like

Yeah It did now :frowning:

Can anyone tell me the recursive solution