Problem Link:

First DP problem for me in SPOJ. But was not that difficult. So the problem is much similar to rod cutting problem in CLRS. But as the range can reach to 1000000000, so direct usage of integer won’t work. Initially I tried using divide and conquer took much time to get the output for 1000 000 000 and after I got the solution the answer my program shows in negative(which is garbage value). So changed divide and conquer to DP solution using BigInteger, that’s it one go AC 🙂

Solution Link: