Hello everyone.
My name is MD AL AMIN BHUIYAN. I was trying to get some knowledge about dynamic
programming. During my learning period, I tried to gather all resources in one place and also make
a list of my solved problems day by day. So if I get any improvement or anything good in my
process this is the path that I will show to others and so on.
Sorry for my poor English. Let’s move on to my next point.
I searched a lot of videos on YouTube. Every resource has different types of specialty. I made up
my mind to follow a particular one.
First I have watched the video mentioned below for a specific guideline.
Motivation and guideline:
https://www.youtube.com/watch?v=WV5vI_p0L9Q&list=PLzVLIdIx9dQxwAN5mMkzdvK2B4rV8879j&ind
ex=2
In this video, there are some resources in the description which I have also copied here. After getting
this information I have watched Aditya Verma’s playlist. Here I also like to mention that his recursion
playlist is very efficient. This playlist is suggested by my friend Hasan. I learned recursion before so I
didn’t watch it during my learning time.
Aditya Verma’s DP Playlist: https://www.youtube.com/playlist?list… (Hindi)
Before solving new problems I watched the lectures of Errichto on youtube. You can see in my
solved problems list that I mentioned the lecture number before solving the specific problem.
Errichto Lectures:
1. https://www.youtube.com/watch?v=YBSt1jYwVfU
2. https://www.youtube.com/watch?v=1mtvm2ubHCY
3. https://www.youtube.com/watch?v=KJWAQVmuFW0
LCS blog: https://www.programiz.com/dsa/longest-common-subsequence
Edit Distance Blog: https://www.techiedelight.com/levenshtein-distance-edit-distance-problem/
LIS blog: https://cp-algorithms.com/sequences/longest_increasing_subsequence.html
Some tricks and realizations during my learning time. You can just roll your eyes at the points
mentioned below:
My friend Hamim said to remember 3 things to solve DP: (these 3 points are difficult to understand
by reading. Come to me I will show it with an example)
1. States
2. Base case
3. Formula (recursive case)
Hamim told me to search for these 3 points in my solution idea. First look for the states you want to
declare in the bound. Find the base case when will your recursion stop. Finally, make a formula for
the solution.
There are some observations that I have achieved during my learning period. I am
going to mention them, including the day number. These points may or may not be
understood so you can just go through the points:
● The base case doesn't always return 0(zero). There might be some conditions to
returning zero/one otherwise returns the max/min value. (Realization from day 19th)
● For the “number of ways” problems, we need to sum the answer in the recursive case.
(Day 22)
● On day 23rd I learned memory optimization. I saw a video in my native
language(Bangla).
Link: https://www.youtube.com/watch?v=GoV0Gm7iuWI&t=836s
● On day 25th I learned to store the path of my recursive dp.
● On day 27th, I solved my first dp problem in a virtual contest. Hope the real contest
goes up.
● On day 31st, I solved the first Dp problem in the contest.
● Sometimes it is better to memorize the dp array with max values or min values(day 32)
● On day 33 I thought not to use a condition while it was very important and impactful
Here are the links to the resources mentioned in the guideline video:
Hackerearth’s 4 DP Tutorials:
https://www.hackerearth.com/practice/...
Codechef:
https://www.codechef.com/cptutorials?...
DP Playlist:
https://www.youtube.com/playlist?list...
CSES: https://cses.fi/problemset/
ATCODER: https://atcoder.jp/contests/dp
USACO guide gold: https://usaco.guide/gold/
USACO guide platinum: https://usaco.guide/plat/
USACO guide advanced: https://usaco.guide/adv
Solved Problems:
Day Problem link Concept
1 After watching Errichto’s first lecture: Fibonacci
https://atcoder.jp/contests/dp/tasks/dp_a
https://atcoder.jp/contests/dp/tasks/dp_b
https://atcoder.jp/contests/dp/tasks/dp_c
2-3 After watching Eriichto’s 2nd lecture: Coin Change
https://cses.fi/problemset/task/1633 Coin Combinations
https://cses.fi/problemset/task/1634
https://cses.fi/problemset/task/1635
https://cses.fi/problemset/task/1636
4 After reading Kadane’s algorithm:
https://cses.fi/problemset/task/1643
After learning Hamim’s Formula:
https://codeforces.com/contest/1373/problem/D
https://codeforces.com/contest/118/problem/D
5 https://atcoder.jp/contests/abc220/tasks/abc220_d 2D Fibonacci
6 https://www.codechef.com/problems/TSOH Kadane’s algorithm
7-11 https://atcoder.jp/contests/dp/tasks/dp_d
https://atcoder.jp/contests/dp/tasks/dp_e
https://cses.fi/problemset/task/1158 Knapsack
https://cses.fi/problemset/task/1745
https://cses.fi/problemset/task/1093
12 https://codeforces.com/problemset/problem/106/C Knapsack
13 https://codeforces.com/contest/730/problem/J Knapsack
14-15 Errichto Lecture 3 and LCS blog:
https://atcoder.jp/contests/dp/tasks/dp_f Longest Common
https://lightoj.com/problem/an-easy-lcs Subsequence
16 Edit distance blog(Recursive ideas sound cool):
https://cses.fi/problemset/task/1639/ Edit Distance
https://www.spoj.com/problems/MC/
17 https://codeforces.com/contest/1324/problem/E Coin change
18 https://codeforces.com/contest/358/problem/D Knapsack
https://codeforces.com/contest/225/problem/C
19 https://codeforces.com/contest/234/problem/F Knapsack
20 https://codeforces.com/contest/67/problem/D LIS
https://codeforces.com/contest/214/problem/E Recursion/Subproblem
21 https://lightoj.com/problem/pimp-my-ride Bitmask Dp
22 https://lightoj.com/problem/divisible-group-sums No of ways
23 https://codeforces.com/contest/1625/problem/C Memory optimization
24 https://lightoj.com/problem/how-many-zeroes Digit Dp
25 https://codeforces.com/contest/1624/problem/E Dp and Backtrack
26 https://codeforces.com/contest/1633/problem/D Knapsack
27 https://codeforces.com/contest/1207/problem/C 0/1 knapsack
28 https://codeforces.com/contest/909/problem/C Iterative and prefix sum
29 https://codeforces.com/contest/1061/problem/C Space and Time
optimization
30 https://codeforces.com/contest/5/problem/C DP, Greedy, Constructive
31 https://codeforces.com/contest/1681/problem/D Shortest path dp
32 https://codeforces.com/gym/104059/problem/I
33 https://atcoder.jp/contests/abc303/tasks/abc303_d
34 https://www.codechef.com/problems/CS2023_404 IDEA
