mac_n_cheese_pog's blog

How to guess for dp states?
By mac_n_cheese_pog, history, 3 years ago, In English

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?

  • Vote: I like it
  • -33
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

pls help

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

"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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You need "prefix of the array / string" as a state in $$$90\%$$$ of problems.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply