please explain the question…
Okay, So as told, friend lives in 1st street and Chef in Nth street. You have find the path such that it has minimal product following the condition 1<=Y-X<=K.
This problem simply boils down to standard problem- “Find the minimum cost path from one node to another”. Here the cost is simple the product of the weights of the path.
This problem can be solved by basic dp and sliding window. Just find the minimum value stored in the previous K indices. So we need to find the minimum in the range (i-K+1,i). So just maintain a the minimum in the window for every range.
1 Like
Hope it clears you doubt.
1 Like
ya …thanks a lot!!
1 Like