Please help! Frequently coming doubt to my mind in one famous DP(Knapsack) problem ??

Правка en3, от helloworld1102, 2023-10-14 22:31:59

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.

Atcoder example problem

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский helloworld1102 2023-10-14 22:31:59 11 Tiny change: 'bvious is not enough intuitive' -> 'bvious is intuitive'
en2 Английский helloworld1102 2023-10-14 22:30:48 31
en1 Английский helloworld1102 2023-10-14 22:29:51 1283 Initial revision (published)