Блог пользователя mac_n_cheese_pog

Автор mac_n_cheese_pog, история, 3 года назад, По-английски

I've practiced for dp and i have found my weakness.its the dp state.somehow i never guessed it correctly.the states that i made was never relevant to the actual answer.its totally wrong.i have no clue whenever i try to make some dp states and just see if somethings correct.idk how poeple just solve dp like its 1+1.i do not know what do memoize.can someone help me?

  • Проголосовать: нравится
  • -33
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

pls help

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

"the states that i made was never relevant to the actual answer"

its because one should not guess dp states, instead one should derive it using recurrence relation.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How? or perhaps my elaboration is not that clear.lemme make an example.

    take a classical LCS

    we have 2 strings.with those strings we need to check the lcs.ofc bruteforce will come to mind first but it requires tons of loops and other things.WIth dp,we need to observe.but whenever i observe,its wrong.like for example,what do we need? the position of a specific characters? the number of occurence of a letter? the length? well idk unless soomeone tell me what matters.i would always guess.

    lcs might be a bit obvious but think about more advance

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Think like this — Let currently you are at index i so what are the necessary information you should know from previous values to calculate the answer of current i, those informations will be your state of dp. You can always optimise your states from here.