Hello,there I know it's a irrelevant question to some of you .But, I want to ask as I have spent a long time and have a feeling that this DP approach could be correct(I think so) . But , yeah it could also be wrong and I want to ask why it can be wrong? So, yeah here it goes -->
Let dp(i,pos) = Min no of days to get money i and in getting money i optimally you reached the position pos.
And here will be the transitions according to me
dp(i,pos)--> dp(i + a[pos],pos) OR --> dp(i-b[pos],pos+1)
WHERE a and b are the arrays given in the question and the answer will be the DP[c][x] ( c is the total cost of new computer and x lies in range from position 1 to N in the array and we will take minimum dp of that.)
This is what I have thought of this question after spending some time . And I think time complexity will be in N^2 but I am interested whether this approach will lead to right answer. If not I really want to know the reason why it will fail?
I know some people can think it is rude to write a whole blog on it you can just ask in the comments but this round happened months ago so I will not get answer quickly.So I asked here.
Thank you everyone
Problem Link
I believe this can be an approach to solve this problem, but is not feasible to do so. The Time complexity will be O(c*n) not O(n*n). Which will get TLE.
Memory I think can be reduced from O(c*n) to O(c),but even after that we will get MLE.