Is my approach of 1512F (Education) using DP correct?(Does it make sense) if not why ?

Revision en1, by helloworld1102, 2021-11-10 17:26:28

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English helloworld1102 2021-11-10 17:26:28 1282 Initial revision (published)