Beginner Friendly Series on Dynamic Programming || CSES, Codeforces, Kick start etc

Revision en2, by kartik8800, 2020-07-14 03:29:12

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.

Problem 1: Dice Combinations

Source: CSES
Problem link: https://cses.fi/problemset/task/1633
Explanation: https://youtu.be/5gd5jptXWAM

Problem 2: Coin Combinations I

Source: CSES
Problem link: https://cses.fi/problemset/task/1635
Explanation: https://youtu.be/5BdAl6gfusg

Problem 3: Coin Combinations II

Source: CSES
Problem link: https://cses.fi/problemset/task/1636
Explanation: https://youtu.be/-pXjopzMVrE

Problem 4: Grid Paths

Source: CSES
Problem link: https://cses.fi/problemset/task/1638
Explanation: https://youtu.be/V64F4wlodUM

Problem 5: Book Shop

Source: CSES
Problem link: https://cses.fi/problemset/task/1633
Explanation: https://youtu.be/qpNy2nuSuaI

Problem 6: Array Description

Source: CSES
Problem link: https://cses.fi/problemset/task/1158
Explanation: https://youtu.be/d1H5JylYG4I

Problem 7: Edit Distance

Source: CSES
Problem link: https://cses.fi/problemset/task/1639
Explanation: https://youtu.be/Ev80c1oIRFg

Problem 8: Rectangle Cutting

Source: CSES
Problem link: https://cses.fi/problemset/task/1744
Explanation: https://youtu.be/LdynQjWsO5Q

Problem 9: Two Sets II

Source: CSES
Problem link: https://cses.fi/problemset/task/1093
Explanation: https://youtu.be/TOsD3BkIKoQ

Problem 10: Beautiful Array

Source: Codeforces
Problem link: https://mirror.codeforces.com/problemset/problem/1155/D
Explanation: https://youtu.be/IgBLv32QFoQ

Problem 11: Number of Valid Arrays

Source: Coding Interview
Problem link: Problem Statement
Explanation: https://youtu.be/QGJXQAaDs3I

Problem 12: Longest Increasing Subsequence O(NlogN)

Source: CSES
Problem link: https://mirror.codeforces.com/problemset/problem/1155/D
Proof and optimization to NlogN: https://youtu.be/66w10xKzbRM
Implementation of the algorithm: https://youtu.be/wqLwv7E1GF0

Problem 13: Beauty of Tree

Source: Kick Start
Problem link: Long link
Explanation: https://youtu.be/ueLRceYVcdE

Problem 14: 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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English kartik8800 2021-01-07 13:59:52 332
en6 English kartik8800 2020-12-12 17:47:12 370 Tiny change: 'odeforces -> rated:2400<br>\nProb' -> 'odeforces (rated:2400)<br>\nProb'
en5 English kartik8800 2020-07-25 01:19:16 485
en4 English kartik8800 2020-07-17 11:12:47 939 Tiny change: 'rivation).\n\n\nProb' -> 'rivation).<br>\n\n\nProb'
en3 English kartik8800 2020-07-15 22:39:12 591
en2 English kartik8800 2020-07-14 03:29:12 657
en1 English kartik8800 2020-07-13 02:02:50 3612 Initial revision (published)