meet2410shah's blog

By meet2410shah, 4 years ago, In English

Recently, I have been exposed to Digit DP SPOJ Problems, then I realized that yes, there is a wide range of problems that can be solved using the different dynamic programming approaches. When I first encounter the problem Help Bob, I was totally clueless that how I approach that problem. Then a friend (nishant403) told me to learn the concept of Digit DP. After searching a lot get some insights into it.

There are a lot more techniques like this that are there. I need help to get the whole set of DP Techniques that can be used for Competitive Programming and tutorial related to that with the practice problems that a beginner needs to solve in order to be the tourist of DP. I also need help to determine the specific order in which one needs to learn these techniques that increase the difficulty gradually.

Here are some of the posts that I found related to Dynamic Programming.
General DP:
1. Everything About Dynamic Programming.
2. DP Tutorial and Problem List.

DP on Trees and Rerooting:
1. DP on Trees Tutorial.
2. Online Query Based Rerooting Technique.

Digit DP:
1. Digit DP.
2. DIGIT DP Tutorial [ITERATIVE].
3. Digit Dp + Matrix Chain Multiplication.

DP with Bitmasking:
1. Introduction to DP with Bitmasking.

As of now, these are the list of articles that I found on codeforces. I will keep updating the list of articles. Hope for great support. Thanks a lot to all of them who have written these useful articles that enhance the knowledge.

Thank You.

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by meet2410shah (previous revision, new revision, compare).

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

I've seen many hard (for me) DP problems where the hard part is "just" trying task-specific ways reduce the number of states, e.g. in https://boi2019.eio.ee/wp-content/uploads/2019/05/kitchen.en_.pdf

Another example is a chinese problem I failed to solve once (my translation here, but it was just for me so it's kind of sparse https://github.com/ldct/cp/blob/master/luogu/SWTR-05/A/A.pdf) where the standard DP is O(N^5) but you have to reduce it down to O(N^2) through reducing the number of states + precomputation