Why is Dynamic Programming hard and important?

general
1

This time in June Cookoff (Contest Page | CodeChef) I noticed that 3 out of 5 problems use dynamic programming at its core. I am learning basic dynamic programming from past one week but still, I am not able to crack the cookoff questions. I googled similar problems but was only able to find similar problems which were not much similar to get an AC. This sometimes demotivates me and forces me to think “Beta Kuch bhi karle jab lode lagne honge to lag ke rhenge”. Ab is samsya ka kya samadhan hai?

1 Like
2

Dynamic Programming is a difficult topic to master and you have given it only a week. There are people who have practiced around 200 - 300 questions on dynamic programming and still get stuck. Don’t feel demotivated. Just keep practicing and you will eventually be able to solve these questions.
To learn DP, firstly practice standard DP questions like knapsack, MCM, LCS, LIS, e.t.c. Then solve question from a2oj DP problemset. There are many more resources available on the internet as well.

7 Likes
3

solved 4/5 by brute or simple logic. First understand if the problem really requires DP or not…Also please refrain from discussing during contest.

7 Likes
4

This will help you a lot…

3 Likes
5

“dynamic programming at its core”
Lol :rofl::rofl:

5 Likes
6

First things first , it makes 0 sense to discuss a problem or rant about it during a contest . Secondly certainly first 4/5 problems of Div 2 dont use dp . Thirdly and most importantly start practicing and stop Writing about in the MIDDLE of a contest about it and @awaracoder has given u a fair amount of resources for the same.

2 Likes
7

you have shared a very important source , i didn’t knew about it . Thank you.

1 Like
8

Here some must do dp problems. see the dp section basic and advance

9

Samasya ka samadhan is read editorials after contest then you will realize what was the expected approach

2 Likes
10

Same here.:smiley::smiley:

But I think it was not a great contest as usually 4th question of cook off involves some good DS or algorithm.

1 Like
11

Which are the 3 out of 5 questions that used DP…?

1 Like
12

Last 3 problems. I know that these can be solved using another approach (if you are successful in coming up with it, I wasn’t). But as a novice to DP, I ask ain’t problems involving maximising and minimising aren’t meant to be easily be solved using DP?

13

problem 3 was a greedy approach question