Beginner Friendly Series on DP(Added DP with bitmasks)

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

  1. What is Divide and Conquer?
  2. What is Dynamic Programming?
  3. Types of DP problems.

Part 2: https://youtu.be/yfgKw6BUZUk

  1. What is a DP-state?
  2. Characterizing a DP-state.
  3. What is a recurrence?
  4. Top Down v/s Bottom Up.

Part 3: https://youtu.be/X-3HklSPx6k

  1. Directed Acyclic Graph(DAG) Representation of DP solution
  2. Visualizing Top-Down and Bottom-Up.
  3. Evaluation order for bottom-up codes.
  4. Analyzing the space and time complexity for a DP solution(derivation).

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: Removing Digits

Source: CSES

Problem link: https://cses.fi/problemset/task/1637

Explanation: https://youtu.be/32qvB7OP4V8

Problem 5: Grid Paths

Source: CSES

Problem link: https://cses.fi/problemset/task/1638

Explanation: https://youtu.be/V64F4wlodUM

Problem 6: Book Shop

Source: CSES

Problem link: https://cses.fi/problemset/task/1633

Explanation: https://youtu.be/qpNy2nuSuaI

Problem 7: Array Description

Source: CSES

Problem link: https://cses.fi/problemset/task/1158

Explanation: https://youtu.be/d1H5JylYG4I

Problem 8: Edit Distance

Source: CSES

Problem link: https://cses.fi/problemset/task/1639

Explanation: https://youtu.be/Ev80c1oIRFg

Problem 9: Rectangle Cutting

Source: CSES

Problem link: https://cses.fi/problemset/task/1744

Explanation: https://youtu.be/LdynQjWsO5Q

Problem 10: Two Sets II

Source: CSES

Problem link: https://cses.fi/problemset/task/1093

Explanation: https://youtu.be/TOsD3BkIKoQ

Problem 11: Beautiful Array

Source: Codeforces

Problem link: https://codeforces.com/problemset/problem/1155/D

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: https://codeforces.com/problemset/problem/1155/D

Proof and optimization to NlogN: https://youtu.be/66w10xKzbRM

Implementation of the algorithm: https://youtu.be/wqLwv7E1GF0

Problem 14: Projects

Source: CSES

Problem link: https://cses.fi/problemset/task/1140

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.

23 Likes

UPD: added 2 problems.

UPD : Added 3 parts on basic elements of DP to get you started.

Nice Videos. Keep Adding videos thanks.

1 Like

Keep adding videos. I have subbed, will watch them when I am done with my current queue. Nice handwriting, btw :wink:

1 Like

Surely!

wait a second have I seen this compliment somewhere xD
by the way, thanks and I hope you will find the content useful and interesting.

1 Like

I will find it useful AND interesting. I have glanced through one of your videos. I am not doing it right away I use queue data structure not stack.

P.S. Yes, you know me :slight_smile:

1 Like

Thanks very helpful videos!

1 Like