Dynamic programming – the one thing that makes every participant in competitive programming scratch their heads. In general, most programming competitions will have one dynamic programming question. It can be referred to as the problem which is there for the win. Solve it correctly and you are likely to win the grand prize.
Plus, it’s difficult and so, it is likely that many of your competitors will not be able to solve it. Dynamic programming (DP) is tricky – there’s no doubt about that. It has overlapping subproblems, each of which has to be solved just once. All of it sounds very challenging. However, there are a few tips you can follow to ace Dynamic Programming in competitions:
There are many online tutorials designed to teach you dynamic programming properly. When you are going through these tutorials, you will come across many new terms like iterative code, memoization, recursive code, etc. Research about them and see how they are implemented in the program.
You can also go through a few suggestions and examples given in these tutorials. Even though you might find DP interesting, many overlapping subproblems may not be straightforward. For example, there are DP with Bitmasks, Digit DP, etc. Learn more about these complex programming parts too in different tutorials.
Breaking it up
When you are solving DP, you have to make up a mindset – to think in terms of globally optimal choices. Do not think locally. That’s the secret. When you come across DP, start breaking it down into simpler subproblems and then solve each of them once. Now, build up to the final solution by combining these solved subproblems.
Noting it down
Start exploring the whole search space and make small inputs on paper. When you are solving the problem, these inputs can help you a lot in avoiding iterative. Iterating all the permutations will be extremely ineffective and time-consuming. Rather keep your notebook in hand and start noting down important points as you work through the DP. It will be more logical, less time-consuming and much more effective.
Recursion is a function that calls itself. Now, that’s the bare-bones definition of recursion. However, that’s not all of it. Recursion can also be a thought process. Try to use recursive thinking as a solution to different problems. One of the ways is to figure out the base cases first, even if they are not the simple ones. Try to study a functional language like Haskell, which will help you develop the thought process. When you start thinking recursively, you can easily master recursion.
Practice and Hard work
There is no alternative to practising and hard work, especially when you are dealing with DP. So, visit different competitive programming sites and start practising DP. Start off with the easy ones, get your basics right and then move on to the difficult ones. Work hard on your recursive thinking. The more you practice, the better you will become at identifying a problem as DP and then breaking it down into simpler segments.
Believe in yourself
DP is difficult and tricky, but if you give up from the first, then you won’t be able to tackle it. First, you have to believe in yourself and know that you can engage with Dynamic Programming. Once you believe in yourself, you will be able to work hard and find solutions to difficult problems. It will also help you keep your mind cool and be confident when you finally tackle DP in competitive programming.
Make a schedule and keep a slot for practising DP every day. You might require a guide to help you with DP and make you a true master in it. You can also opt for the Coding Ninjas Competitive Programming course to get expert advice and help with Dynamic Programming.