I agree with you. Most of those tutorials start with bottom-up DP which is believe me not naive to come up with (requires much experience). Though bottom-up DP is more efficient than top-down/recursive DP. But you can easily deduce your top-down solution to the bottom-up. So I would suggest, solve a lot of problems that require recursion and develop recursive thinking. You will get to learn DP as a byproduct. Because DP is an optimization of brute-force/naive recursive solution by memorizing and reusing the result of redundant calls instead of calculating again.

Once you will be able to implement a brute-force solution using recursion then you have to analyze if states are repetitive or not. If yes then just add memoization of results. That's it, you are done. :)

This is the first request for help I've come across which hasn't been downvoted just out of spite and people have actually given some suggestions in comments.

For simple dynamic programming problem, you can just make a correct recursive bruteforce (just dont mind the time limit). Then put all variables that is not considered as constant into function parameters (for which is calculated this time but changed after transiting)

• You have base cases (to stop recursive)

• You have transitions (relationship about those parameters)

• You have the value from those smaller recursive problem

• You just not have the memorization

Therefore, for such parameters that you care in transition, use them as memorization, and then you have a DP solution

So, for practice simple dp problem, you can simply do brute force recursive and then add memorization

But, for harder ones, you have to optimize it in somehow

• Change into iterative dp (in order to apply some other kind of transitions or calculating that recursive cant)

• Changing the transitions (usually math)

• Optimizing the calculating (usually math or data structure)

• Optimizing the memorization (usually data structure)...

• Convert to other kind of problem that solvable with better algorithm

write down the dp formulas on a paper b4 solving problems

There is some standard procedure which has helped me a lot ( most of the times ), I am writing down the procedure here:

1) Identifying the subproblem : This basically means how is your original problem related to a smaller problem but of the same type. Identifying base cases and building up from them also helps.

2) Finding the relation between the problem and subproblem : This is finding out the recursive relation. For this you need to know how the solution of the subproblems should be combined to obtain the solution for the original problem.

3) Deciding a memoization strategy : Decide how you want to store the computed solutions for the subproblems so you can use them for calculating larger problems.

4) Check acyclicity : This means that your problem should not depend on something that is not yet computed, or is to be computed in a later stage.

These are some helpful tips I have learnt from youtubers :

1) Try to do it greedily, if it doesnt work then there are high chances its a DP problem.

2) Look at the constraints, the constraints give you a good idea about the dimension of the dp. For example : 1<=n<=500, 1<=k<=n so you can see that dp[n][k] is possible. On the other hand if n<=50000 , k<=50000 you can straight away stop thinking about dp[n][k] since the constraints are very high.

3) Solve standard problems and lock the concept in your mind forever. A lot of times dp problems are modifications of standard dp problems ( atleast in my rating range ) and so this helps

4) Practice : atcoder , dp problems from here