This series of videos are focused on explaining dynamic programming by illustrating the application of DP through the use of selected problems from platforms like Codeforces, Codechef, SPOJ, CSES and Atcoder.
After going through this series, you should find yourself confident in approaching dynamic programming problems and also implementing them in a reasonable amount of time.
I will also live code and submit the solutions to the problem on the coding platform from where the problem comes.
Some Basic elements of Dynamic Programming
Some general ideas and my thoughts about DP to help you get started:
Part 1: https://youtu.be/24hk2qW_BCU
- What is Divide and Conquer?
- What is Dynamic Programming?
- Types of DP problems.
Part 2: https://youtu.be/yfgKw6BUZUk
- What is a DP-state?
- Characterizing a DP-state.
- What is a recurrence?
- Top Down v/s Bottom Up.
Part 3: https://youtu.be/X-3HklSPx6k
- Directed Acyclic Graph(DAG) Representation of DP solution
- Visualizing Top-Down and Bottom-Up.
- Evaluation order for bottom-up codes.
- Analyzing the space and time complexity for a DP solution(derivation).
Problem 1: Dice Combinations
Source: CSES
Problem link: CSES - Dice Combinations
Explanation: https://youtu.be/5gd5jptXWAM
Problem 2: Coin Combinations I
Source: CSES
Problem link: CSES - Coin Combinations I
Explanation: https://youtu.be/5BdAl6gfusg
Problem 3: Coin Combinations II
Source: CSES
Problem link: CSES - Coin Combinations II
Explanation: https://youtu.be/-pXjopzMVrE
Problem 4: Removing Digits
Source: CSES
Problem link: CSES - Removing Digits
Explanation: https://youtu.be/32qvB7OP4V8
Problem 5: Grid Paths
Source: CSES
Problem link: CSES - Grid Paths
Explanation: https://youtu.be/V64F4wlodUM
Problem 6: Book Shop
Source: CSES
Problem link: CSES - Dice Combinations
Explanation: https://youtu.be/qpNy2nuSuaI
Problem 7: Array Description
Source: CSES
Problem link: CSES - Book Shop
Explanation: https://youtu.be/d1H5JylYG4I
Problem 8: Edit Distance
Source: CSES
Problem link: CSES - Edit Distance
Explanation: https://youtu.be/Ev80c1oIRFg
Problem 9: Rectangle Cutting
Source: CSES
Problem link: CSES - Rectangle Cutting
Explanation: https://youtu.be/LdynQjWsO5Q
Problem 10: Two Sets II
Source: CSES
Problem link: CSES - Two Sets II
Explanation: https://youtu.be/TOsD3BkIKoQ
Problem 11: Beautiful Array
Source: Codeforces
Problem link: Problem - 1155D - Codeforces
Explanation: https://youtu.be/IgBLv32QFoQ
Problem 12: Number of Valid Arrays
Source: Coding Interview
Problem link: Problem Statement
Explanation: https://youtu.be/QGJXQAaDs3I
Problem 13: Longest Increasing Subsequence O(NlogN)
Source: CSES
Problem link: Problem - 1155D - Codeforces
Proof and optimization to NlogN: https://youtu.be/66w10xKzbRM
Implementation of the algorithm: https://youtu.be/wqLwv7E1GF0
Problem 14: Projects
Source: CSES
Problem link: CSES - Projects
Solution Approach: https://youtu.be/MJn3ogwsUbo
Implementation of the algorithm: https://youtu.be/ISuIwMnSyXc
Problem 15: Beauty of Tree
Source: Kick Start
Problem link: Long link
Explanation: https://youtu.be/ueLRceYVcdE
Problem 16: Catch Some
Source: Kick Start
Problem link: Long link
Explanation: https://youtu.be/ljLIrNKLANE
I am quite confident that many beginners/intermediates will definitely enjoy watching this series on dynamic programming and it will definitely help in getting better at dynamic programming and problem solving in general. I have tried to teach in a way such that not many prior prerequisites are required to understand the explanations even to the harder problems.
If people find this helpful then I will make sure that this list of problems will keep growing, cheers!
UPD: Added 2 more problems from CSES: Projects and Removing digits.
UPD: Added 3 parts on basic elements of DP to get you started.
