Hello Codeforces!↵
↵
This series of videos are focused on explaining dynamic programming by illustrating the application of digit 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 solving problems which require the use of digit dp 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>↵
↵
You may also want to checkout these video tutorials:<br>↵
- [Beginner Friendly Series on Dynamic Programming](https://codeforces.net/blog/entry/80064)<br>↵
- [Dynamic Programming on Trees](https://codeforces.net/blog/entry/79857)<br>↵
- [Introduction to DP with Bitmasking](https://codeforces.net/blog/entry/81516)↵
↵
↵
↵
Introduction to Digit DP↵
------------------↵
↵
I discuss the following concepts in this video:↵
↵
1. What exactly is Digit DP?<br>↵
2. What are the types of problems I can solve with Digit DP?<br>↵
3. Discussing a sample problem and it's brute force solution.<br>↵
4. Building up an intuition towards a DP based solution.<br>↵
5. Further discussing another concept required for solving Digit DP problems.<br>↵
6. Coding the solution which we came up with.↵
↵
video link: [https://youtu.be/heUFId6Qd1A](https://youtu.be/heUFId6Qd1A)↵
↵
↵
Google Kick Start Round H 2020: Boring Numbers↵
------------------↵
I'll discuss a problem named boring numbers that comes from a Google kick start round.<br>↵
Problem link: [google kick start problem](https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff49/000000000043b0c6#problem)<br>↵
Solution: [https://youtu.be/2yAEj-0A8bk](https://youtu.be/2yAEj-0A8bk)↵
↵
↵
SPOJ: Digit Sum↵
------------------↵
Problem link: [https://www.spojcodechef.com/problems/PR003004/ENCODING](https://www.spojcodechef.com/problems/PR003004/ENCODING)<br>↵
Solution: [https://www.youtube.com/watch?v=H6OCV7qcZoQ](https://www.youtube.com/watch?v=H6OCV7qcZoQ)↵
↵
Codechef long: Encoding↵
------------------↵
Problem link: [https://www.spoj.com/problems/PR003004/](https://www.spoj.com/problems/PR003004/)<br>↵
Solution: [https://youtu.be/B7ZWUBfaIq0](https://youtu.be/B7ZWUBfaIq0)↵
↵
↵
↵
<b>Practice Problems:</b><br>↵
1. https://www.spoj.com/problems/CPCRC1C/ <br>↵
2. https://www.spoj.com/problems/NUMTSN/ <br>↵
3. https://www.spoj.com/problems/PR003004/ <br>↵
4. https://codeforces.net/contest/628/problem/D <br>↵
5. https://codeforces.net/gym/100886/problem/G <br>↵
↵
↵
Will be adding more videos soon! <br>↵
Hope people find this helpful :)↵
↵
<b>UPD:</b> added spoj digit sum and codechef enocding. This is the last video for this series(at least for now) unless there are many people who want more.
↵
This series of videos are focused on explaining dynamic programming by illustrating the application of digit 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 solving problems which require the use of digit dp 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>↵
↵
You may also want to checkout these video tutorials:<br>↵
- [Beginner Friendly Series on Dynamic Programming](https://codeforces.net/blog/entry/80064)<br>↵
- [Dynamic Programming on Trees](https://codeforces.net/blog/entry/79857)<br>↵
- [Introduction to DP with Bitmasking](https://codeforces.net/blog/entry/81516)↵
↵
↵
↵
Introduction to Digit DP↵
------------------↵
↵
I discuss the following concepts in this video:↵
↵
1. What exactly is Digit DP?<br>↵
2. What are the types of problems I can solve with Digit DP?<br>↵
3. Discussing a sample problem and it's brute force solution.<br>↵
4. Building up an intuition towards a DP based solution.<br>↵
5. Further discussing another concept required for solving Digit DP problems.<br>↵
6. Coding the solution which we came up with.↵
↵
video link: [https://youtu.be/heUFId6Qd1A](https://youtu.be/heUFId6Qd1A)↵
↵
↵
Google Kick Start Round H 2020: Boring Numbers↵
------------------↵
I'll discuss a problem named boring numbers that comes from a Google kick start round.<br>↵
Problem link: [google kick start problem](https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff49/000000000043b0c6#problem)<br>↵
Solution: [https://youtu.be/2yAEj-0A8bk](https://youtu.be/2yAEj-0A8bk)↵
↵
↵
SPOJ: Digit Sum↵
------------------↵
Problem link: [https://www.
Solution: [https://www.youtube.com/watch?v=H6OCV7qcZoQ](https://www.youtube.com/watch?v=H6OCV7qcZoQ)↵
↵
Codechef long: Encoding↵
------------------↵
Problem link: [https://www.spoj.com/problems/PR003004/](https://www.spoj.com/problems/PR003004/)<br>↵
Solution: [https://youtu.be/B7ZWUBfaIq0](https://youtu.be/B7ZWUBfaIq0)↵
↵
↵
↵
<b>Practice Problems:</b><br>↵
1. https://www.spoj.com/problems/CPCRC1C/ <br>↵
2. https://www.spoj.com/problems/NUMTSN/ <br>↵
3. https://www.spoj.com/problems/PR003004/ <br>↵
4. https://codeforces.net/contest/628/problem/D <br>↵
5. https://codeforces.net/gym/100886/problem/G <br>↵
↵
↵
Will be adding more videos soon! <br>↵
Hope people find this helpful :)↵
↵
<b>UPD:</b> added spoj digit sum and codechef enocding. This is the last video for this series(at least for now) unless there are many people who want more.
