### mac_n_cheese_pog's blog

By mac_n_cheese_pog, history, 3 years ago,

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

| Write comment?
 » 3 years ago, # |   -6 pls help
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 The more you practice the more intuitive it becomes, most of the time the dimensions depend on the parameter in your recursive approach.
•  » » » 3 years ago, # ^ |   -10 oh wow practice! why i didnt think of that -_-
•  » » » » 3 years ago, # ^ |   +1 Is there any other secret I am unaware of?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 then why not try it? This helped me a lot.
 » 3 years ago, # | ← 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 years ago, # ^ |   0 How? or perhaps my elaboration is not that clear.lemme make an example.take a classical LCSwe 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 years ago, # ^ |   +3 You need "prefix of the array / string" as a state in $90\%$ of problems.
 » 3 years ago, # |   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.