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:<br>↵
↵
Part 1: [https://youtu.be/24hk2qW_BCU](https://youtu.be/24hk2qW_BCU)<br>↵
1. What is Divide and Conquer?<br>↵
2. What is Dynamic Programming?<br>↵
3. Types of DP problems.<br>↵
↵
Part 2: [https://youtu.be/yfgKw6BUZUk](https://youtu.be/yfgKw6BUZUk)<br>↵
1. What is a DP-state?<br>↵
2. Characterizing a DP-state.<br>↵
3. What is a recurrence?<br>↵
4. Top Down v/s Bottom Up.<br>↵
↵
Part 3: [https://youtu.be/X-3HklSPx6k](https://youtu.be/X-3HklSPx6k)<br>↵
1. Directed Acyclic Graph(DAG) Representation of DP solution<br>↵
2. Visualizing Top-Down and Bottom-Up.<br>↵
3. Evaluation order for bottom-up codes.<br>↵
4. Analyzing the space and time complexity for a DP solution(derivation).<br>↵
↵
↵
Problem 1: Dice Combinations↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1633<br>↵
Explanation: [https://youtu.be/5gd5jptXWAM](https://youtu.be/5gd5jptXWAM)↵
↵
Problem 2: Coin Combinations I↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1635<br>↵
Explanation: [https://youtu.be/5BdAl6gfusg](https://youtu.be/5BdAl6gfusg)↵
↵
Problem 3: Coin Combinations II↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1636<br>↵
Explanation: [https://youtu.be/-pXjopzMVrE](https://youtu.be/-pXjopzMVrE)↵
↵
Problem 4: Removing Digits↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1637<br>↵
Explanation: [https://youtu.be/32qvB7OP4V8](https://youtu.be/32qvB7OP4V8)↵
↵
Problem 5: Grid Paths↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1638<br>↵
Explanation: [https://youtu.be/V64F4wlodUM](https://youtu.be/V64F4wlodUM)↵
↵
Problem 6: Book Shop↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1633<br>↵
Explanation: [https://youtu.be/qpNy2nuSuaI](https://youtu.be/qpNy2nuSuaI)↵
↵
Problem 7: Array Description↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1158<br>↵
Explanation: [https://youtu.be/d1H5JylYG4I](https://youtu.be/d1H5JylYG4I)↵
↵
Problem 8: Edit Distance↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1639<br>↵
Explanation: [https://youtu.be/Ev80c1oIRFg](https://youtu.be/Ev80c1oIRFg)↵
↵
Problem 9: Rectangle Cutting↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1744<br>↵
Explanation: [https://youtu.be/LdynQjWsO5Q](https://youtu.be/LdynQjWsO5Q)↵
↵
Problem 10: Two Sets II↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1093<br>↵
Explanation: [https://youtu.be/TOsD3BkIKoQ](https://youtu.be/TOsD3BkIKoQ)↵
↵
Problem 11: Beautiful Array↵
------------------↵
Source: Codeforces<br>↵
Problem link: https://codeforces.me/problemset/problem/1155/D<br>↵
Explanation: [https://youtu.be/IgBLv32QFoQ](https://youtu.be/IgBLv32QFoQ)↵
↵
↵
Problem 12: Number of Valid Arrays↵
------------------↵
Source: Coding Interview<br>↵
Problem link: [Problem Statement](https://docs.google.com/document/d/1_01rKWuqIxSYOqrSBzkj4Ue_AGJMVLBLtLrZX0tCx1Q/edit?usp=sharing)<br>↵
Explanation: [https://youtu.be/QGJXQAaDs3I](https://youtu.be/QGJXQAaDs3I)↵
↵
Problem 13: Longest Increasing Subsequence O(NlogN)↵
------------------↵
Source: CSES<br>↵
Problem link: https://codeforces.me/problemset/problem/1155/D<br>↵
Proof and optimization to NlogN: [https://youtu.be/66w10xKzbRM](https://youtu.be/66w10xKzbRM)<br>↵
Implementation of the algorithm: [https://youtu.be/wqLwv7E1GF0](https://youtu.be/wqLwv7E1GF0)↵
↵
Problem 14: Projects↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1140<br>↵
Solution Approach: [https://youtu.be/MJn3ogwsUbo](https://youtu.be/MJn3ogwsUbo)<br>↵
Implementation of the algorithm: [https://youtu.be/ISuIwMnSyXc](https://youtu.be/ISuIwMnSyXc)↵
↵
↵
Problem 15: Beauty of Tree↵
------------------↵
Source: Kick Start<br>↵
Problem link: [Long link](https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff08/0000000000386edd) <br>↵
Explanation: [https://youtu.be/ueLRceYVcdE](https://youtu.be/ueLRceYVcdE)↵
↵
Problem 16: Catch Some↵
------------------↵
Source: Kick Start<br>↵
Problem link: [Long link](https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050ff2/0000000000150a0d)<br>↵
Explanation: [https://youtu.be/ljLIrNKLANE](https://youtu.be/ljLIrNKLANE)↵
↵
Problem 17: Vasya and Binary Strings↵
------------------↵
Source: Codeforces (rated:2400)<br>↵
Problem link: [https://codeforces.me/problemset/problem/1107/E](https://codeforces.me/problemset/problem/1107/E)<br>↵
Explanation: [https://youtu.be/NINZAQFW_AE](https://youtu.be/NINZAQFW_AE)↵
↵
↵
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!↵
↵
↵
Link for introduction to DP on Trees: https://codeforces.me/blog/entry/79857<br>↵
↵
<strong>UPD</strong>: Added 2 more problems from CSES: Projects and Removing digits.<br>↵
<strong>UPD</strong>: Added 3 parts on basic elements of DP to get you started.<br>↵
↵
<strong>UPD</strong>: I have also started a series on DP with bitmasking(starting from the very basics) and in the future will make a separate blog for both Digit DP series and DP with bitmasking series, till then interested people can check: [Dynamic Programming with bitmasking](https://www.youtube.com/playlist?list=PLb3g_Z8nEv1icFNrtZqByO1CrWVHLlO5g)<br>↵
<strong>UPD</strong>: added solution to problem Vasya and Binary Strings
↵
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:<br>↵
↵
Part 1: [https://youtu.be/24hk2qW_BCU](https://youtu.be/24hk2qW_BCU)<br>↵
1. What is Divide and Conquer?<br>↵
2. What is Dynamic Programming?<br>↵
3. Types of DP problems.<br>↵
↵
Part 2: [https://youtu.be/yfgKw6BUZUk](https://youtu.be/yfgKw6BUZUk)<br>↵
1. What is a DP-state?<br>↵
2. Characterizing a DP-state.<br>↵
3. What is a recurrence?<br>↵
4. Top Down v/s Bottom Up.<br>↵
↵
Part 3: [https://youtu.be/X-3HklSPx6k](https://youtu.be/X-3HklSPx6k)<br>↵
1. Directed Acyclic Graph(DAG) Representation of DP solution<br>↵
2. Visualizing Top-Down and Bottom-Up.<br>↵
3. Evaluation order for bottom-up codes.<br>↵
4. Analyzing the space and time complexity for a DP solution(derivation).<br>↵
↵
↵
Problem 1: Dice Combinations↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1633<br>↵
Explanation: [https://youtu.be/5gd5jptXWAM](https://youtu.be/5gd5jptXWAM)↵
↵
Problem 2: Coin Combinations I↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1635<br>↵
Explanation: [https://youtu.be/5BdAl6gfusg](https://youtu.be/5BdAl6gfusg)↵
↵
Problem 3: Coin Combinations II↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1636<br>↵
Explanation: [https://youtu.be/-pXjopzMVrE](https://youtu.be/-pXjopzMVrE)↵
↵
Problem 4: Removing Digits↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1637<br>↵
Explanation: [https://youtu.be/32qvB7OP4V8](https://youtu.be/32qvB7OP4V8)↵
↵
Problem 5: Grid Paths↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1638<br>↵
Explanation: [https://youtu.be/V64F4wlodUM](https://youtu.be/V64F4wlodUM)↵
↵
Problem 6: Book Shop↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1633<br>↵
Explanation: [https://youtu.be/qpNy2nuSuaI](https://youtu.be/qpNy2nuSuaI)↵
↵
Problem 7: Array Description↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1158<br>↵
Explanation: [https://youtu.be/d1H5JylYG4I](https://youtu.be/d1H5JylYG4I)↵
↵
Problem 8: Edit Distance↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1639<br>↵
Explanation: [https://youtu.be/Ev80c1oIRFg](https://youtu.be/Ev80c1oIRFg)↵
↵
Problem 9: Rectangle Cutting↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1744<br>↵
Explanation: [https://youtu.be/LdynQjWsO5Q](https://youtu.be/LdynQjWsO5Q)↵
↵
Problem 10: Two Sets II↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1093<br>↵
Explanation: [https://youtu.be/TOsD3BkIKoQ](https://youtu.be/TOsD3BkIKoQ)↵
↵
Problem 11: Beautiful Array↵
------------------↵
Source: Codeforces<br>↵
Problem link: https://codeforces.me/problemset/problem/1155/D<br>↵
Explanation: [https://youtu.be/IgBLv32QFoQ](https://youtu.be/IgBLv32QFoQ)↵
↵
↵
Problem 12: Number of Valid Arrays↵
------------------↵
Source: Coding Interview<br>↵
Problem link: [Problem Statement](https://docs.google.com/document/d/1_01rKWuqIxSYOqrSBzkj4Ue_AGJMVLBLtLrZX0tCx1Q/edit?usp=sharing)<br>↵
Explanation: [https://youtu.be/QGJXQAaDs3I](https://youtu.be/QGJXQAaDs3I)↵
↵
Problem 13: Longest Increasing Subsequence O(NlogN)↵
------------------↵
Source: CSES<br>↵
Problem link: https://codeforces.me/problemset/problem/1155/D<br>↵
Proof and optimization to NlogN: [https://youtu.be/66w10xKzbRM](https://youtu.be/66w10xKzbRM)<br>↵
Implementation of the algorithm: [https://youtu.be/wqLwv7E1GF0](https://youtu.be/wqLwv7E1GF0)↵
↵
Problem 14: Projects↵
------------------↵
Source: CSES<br>↵
Problem link: https://cses.fi/problemset/task/1140<br>↵
Solution Approach: [https://youtu.be/MJn3ogwsUbo](https://youtu.be/MJn3ogwsUbo)<br>↵
Implementation of the algorithm: [https://youtu.be/ISuIwMnSyXc](https://youtu.be/ISuIwMnSyXc)↵
↵
↵
Problem 15: Beauty of Tree↵
------------------↵
Source: Kick Start<br>↵
Problem link: [Long link](https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff08/0000000000386edd) <br>↵
Explanation: [https://youtu.be/ueLRceYVcdE](https://youtu.be/ueLRceYVcdE)↵
↵
Problem 16: Catch Some↵
------------------↵
Source: Kick Start<br>↵
Problem link: [Long link](https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050ff2/0000000000150a0d)<br>↵
Explanation: [https://youtu.be/ljLIrNKLANE](https://youtu.be/ljLIrNKLANE)↵
↵
Problem 17: Vasya and Binary Strings↵
------------------↵
Source: Codeforces (rated:2400)<br>↵
Problem link: [https://codeforces.me/problemset/problem/1107/E](https://codeforces.me/problemset/problem/1107/E)<br>↵
Explanation: [https://youtu.be/NINZAQFW_AE](https://youtu.be/NINZAQFW_AE)↵
↵
↵
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!↵
↵
↵
Link for introduction to DP on Trees: https://codeforces.me/blog/entry/79857<br>↵
↵
<strong>UPD</strong>: Added 2 more problems from CSES: Projects and Removing digits.<br>↵
<strong>UPD</strong>: Added 3 parts on basic elements of DP to get you started.<br>↵
↵
<strong>UPD</strong>: I have also started a series on DP with bitmasking(starting from the very basics) and in the future will make a separate blog for both Digit DP series and DP with bitmasking series, till then interested people can check: [Dynamic Programming with bitmasking](https://www.youtube.com/playlist?list=PLb3g_Z8nEv1icFNrtZqByO1CrWVHLlO5g)<br>↵
<strong>UPD</strong>: added solution to problem Vasya and Binary Strings
