You are viewing a single comment's thread. Return to all comments →
Best possible solution can be found from (min,min-1,min-2). I think we don't need to check for (min-3) and (min-4). I have submitted by calculating optimal from (min,min-1,min-2). Can you provide an example where min-3 or min-4 is more optimal ?
My code :
using namespace std;
left=arr[i]-mn; // for (min)
left=arr[i]-(mn-1); // for (min-1)
left=arr[i]-(mn-2); // for (min-2)
op1=min(op1,op2); // optimal from min-1 and min-2
cout<<min(op1,op3)<<endl; // Most Optimal
generally, in dp solution..we start with 1 and build up our solution till n..but i think here (min,min-1,min-2) will do. how did you conclude that we dont require min-3,min-4. Can you elaborate
There is no need to go till min-3 or min-4. Solution passes all test case with just min, min-1, min-2. Makes sense too, logically. Taking min-1 as baseline is helpful for numbers that are min+4 as they can reach min-1 in 1 step (-5). They couldn't reach min or min-2 in 1 one step.
Similarily, Taking min-2 as baseline is helpful for numbers that are min+3 as they can reach min-2 in 1 step (-5). They would have to take 2 steps in reaching min or min-1.
Taking min-3 as baseline is not helpful for any numbers. min+1 number take 2 steps in reaching there. min+2 number takes one step in reaching (-5) but they could have easily reached min in one step too (-2) . min+3 number take 2 steps in reaching min-3 and 2 steps in reaching min again so we don't really need min-3.
Same logic can be applied for min-4 baseline too.