This is going to be my last blog in codeforces as i am going to quit doing competitive programming.I feel tired of doing it and i figure out i can't stand seeing some people that "worship" cp as their god or something.They only grind and grind without having a life.As the one that is busy nowadays i am unable to keep up with them.So i decided to share about my thoughts on why people don't seem to understand dp quite well.I mean,by making this blog it will enhance my IELTS writing ability and also my knowledge won't go to waste.
Speaking of dynamic programming,we tend to know only some stuff such as recursion and memoization.This is true.However,we can't understand the meaning of dp without knowing a particular topic beforehand,backtracking.
What is backtracking? backtracking is a to get an answer on a specific condition using the previous ones.There are a few conditions to allow backtracking to be executed.This is the reason why dp exists.I will mention them below:
1.There should be some kind of formula that guarantees it's the best option available.
Let's take knapsack as an example.We define dp[i][j] as "in item i and capacity j,which answer would be the best".We only have 2 options,either we take or leave it.This is the thing that make sure dp will be possible.This is one of the form of backtracking.Everything has to be consistent.
2.There should not be a case where the condition broke.
As i've mentioned briefly in the first point,everything has to be the same.You cannot have a case where it can destroys all of the other ones before.Let's consider knapsack again.The reason why knapsack works is because states are only dependent on the previous ones.The future cannot give any impact on the past.For example,dp[i+1][j] will not disturb dp[i][j] by any means.Only dp[i][j] might have the possibility to optimize dp[i+1][j].If we are taking things recursively(which is backtracking),it is the other way around.That is why only 2 flows work,top down and bottom up.
3.There should be a trivial case/base case
In order to make recursion stop,we need to have a non-computable state.This is because,if we don't have an information of something,then it will have infinite recursion.I will take two variables equation for example.If we don't have 2 equations,then we will have an infinite solution for the respective variables.
Okay,i think it should be all for this blog.Hopefully this will help some total noobs out there.The reason i chose this topic is because i don't really see backtracking topics included in a dp section.People tend to miss this crucial concept as a beginner.Alright,this will be the end for now and feel free to help newbies in the comment section.Although,don't contact me to make me revise something on this blog because i won't read them(i quit smh).Anyways,bye everyone :D
