Hello, It can seem strange to ask this question to some of you but I am actually not getting convinced or not something very obvious is intuitive to me. So below is the problem :
The question: Why in knapsack we always chose prefix instead of something like range (l,j). Before you get angry please read my full question.
Like how we are so sure that in taking the prefix of the items we are going to consider all the cases possible that are also lying same if we consider range of the items.
Like in this problem we have to count the different pairs of permutations whose similarity is equal to K .
In the editorial, DP is defined by considering the prefix instead of something like range (I,J). And this is not intuitive to me ?
So in a way the question can be rephrased as How we have to decide in DP when to take prefix and when to take range of the array with the thought in mind that no cases are left out as in case of the above problem example I have given??
If any one can reply it will be of great help to me as this part is not very intuitive/convincing to me.
It's better to think of it like asking question: "For each element, what happens if I include it or not?". Of course, since you are considering elements 1 by 1, it will inevitably form some sort of "prefix" that you are adding to. But that is not the main idea of knapsack.
Thank you very much nonrice, for your reply and effort.