↓Skip to main content
  1. Sipping Go/

Dynamic Programming Algorithms Master Course (2022)

·4 mins
Table of Contents

Assuming you have leared that Dynamic programming is your obstacle, after taking this course, you will thank me.

Course Syllabus #

Introduction #

  • Introduction
  • Instructions

[Optional] Setting Up Coding Environment #

  • Sublime Setup
  • Add Master Header File
  • Escaping Online Judges
  • Common Code Snippets
  • Using Macros
  • Example Code

Basics of Recusion #

  • Recursion Introduction
  • Factorial
  • Fibonacci
  • Sorted Array
  • Increasing Decreasing Number
  • Power Function
  • Power Function Fast
  • Tiling Problem
  • Count Strings
  • Friends Pairing Problem
  • Tower Of Hanoi
  • Tower Of Hanoi (code)

Backtracking #

  • Backtracking Introduction
  • Finding Subsets
  • Finding Subsets Code
  • N-Queen
  • N-Queen Backtracking Code
  • N-Queen Count Ways
  • Generate Brackets
  • Generate Brackets Code
  • Sudoku Solver
  • Suodoku Code
  • Hamiltonian Paths Backtracking
  • Hamiltonian Paths Backtracking (code)
  • Assignments

Introduction to Dynamic Programming #

  • Terms and Definitions
  • Tabulation vs Memoisation
  • Recursion is Everywhere - I
  • Recursion is Everywhere - II
  • Big TIP

1-D Dynammic Programming #

  • Introduction
  • SUPW (Zonal Computing Olympiad)
  • SUPW (code)
  • IPL
  • Min steps to reach one
  • Alphacode
  • Alphacode (code)
  • Rod Cutting
  • Rod Cutting (code)
  • House Robber
  • Palindromic Partioning
  • Assignments

2-D DP Deep Dive : SubSet Sum Problem #

  • Subset Sum (problem)
  • Subset sum (code)
  • Subset Sum with Repeating Numbers
  • Subset Sum Repeating Numbers (code)
  • Subset Sum (Tabulation)
  • Subset Sum Tabulation (code)
  • Memory Optimisation - Subset Sum
  • Memory Super Optimisation - Subset Sum
  • Tracing Back Solutions
  • Modulo Sum (codeforces)
  • Assignments

2D DP: Deep Dive Knapsack Problem #

  • Introduction and greedy approaches
  • 0/1 Knapsack
  • Knapsack (code)
  • 0/N Knapsack
  • Colourful Knapsack

2D DP problems #

  • Paint House
  • Paint House (code)
  • Paint House(follow up)
  • Make Fence Great Again (codeforces)
  • Assignments

Partition Problems #

  • Plates
  • Plates (code)
  • Best Time to Buy and Sell Stock
  • Best Time to Buy and Sell Stock (code)
  • Partition Array for Maximum Sum
  • Partition Equal Sum Subset
  • Split Array largest Sum
  • Split Array Largest Sum (code)
  • Palindromic Partitioning 2
  • Palindromic Partitioning 2 (code)
  • Assignments

Combinatorics and Dynammic Programming #

  • Tiling Problem - 1
  • Tiling Problem - 2
  • Tiling problem - 3
  • Tiling Problem - 3 (code)
  • Advance Tiling problem (SPOJ - M3TILE) with code
  • Number of jumps to reach n
  • Binomial Coefficients
  • Friends pairing Problem
  • Partition N into positive integers
  • Ordered Pair (code)
  • Unordered Pair (code)
  • Solved! Unordered Pair (another recurrence relation)
  • Assignments

Subsequences and Dynammic Programming #

  • Longest Increasing Sequences
  • Longest Increasing Sequence (code)
  • Good Sequences
  • Good Sequences (code)
  • Consecutive Sequences
  • Consecutive Sequences (code)
  • Assignments

K - Dimensional Dynammic Programming #

  • Multi - Dimensional DP
  • Assignments

Digit Dynammic Programming #

  • Introduction
  • Recursive Code
  • Sum Of Digits
  • Investigation + Code
  • Tricks involved
  • Typo! sorry
  • Magic Number (codeforces)
  • Magic Number (code)
  • Nit pick
  • Assignments

Dynammic Programming on Trees #

  • Introduction
  • Vertex Cover (greedy)
  • Definitions and Rules
  • Vertex Cover DP
  • DP code (Recursion + Memoisation)
  • DP on trees using DFS
  • DP on trees using BFS
  • Tree Diameter (cses)
  • Tree Diameter (code)
  • Tree Diameter (NitPick)
  • Distance Tree 1 (CSES)
  • Distance Tree 1 (code)
  • Tree Distance 2
  • Tree Distance 2 (code)
  • Assignments

Trees and Lowest Common Ancestors (DP) #

  • Company Queries 1
  • Binary Lifting using Dynamic Programming
  • Company Queries 1(code)
  • LCA
  • Assignments

Dynammic Programming on Graphs #

  • Intro
  • DFS Tree and Backedges
  • DFS Tree and Backedges (code)
  • DFS Trees and Backedges in Directed Graphs
  • Intro to Articulation Points and Bridges
  • DP - Discovery Time
  • Lowest Time
  • Articulation Point and Bridges concept
  • Articulation Point and Bridges(code)
  • Assignments

DP on Strings #

  • Edit Distance
  • Edit Distance code (top-down)
  • Edit distance (bottom up)
  • Longest Common Subsequence
  • Longest Common Substring
  • Wildcard Pattern Matching
  • Wildcard Pattern Matching (code)
  • Regular Expression Matching
  • Regular Expression Matching Code
  • Interleaving Strings
  • Interleaving Strings (code)
  • Palindromic Substrings
  • Longest Palindromic Subsequences
  • Assignments

Dynammic Programming with Bitmasks #

  • Bit Manipulation Basics
  • Hamiltonian Paths
  • Hamiltonian Paths - Recursion + Memoisation Code
  • Changing Iteration over permutations to iteration over subsets
  • Binary masking factorials
  • Bitmask For Optimisations
  • Bitmask For Optimisations (Code)
  • Dp Bitmasking Bottom Up Code
  • Optimal Selection
  • Optimal Selection code
  • Elevator Problem
  • Elevator Problem (code)
  • Must Try

SOS DP #

  • Note
  • Intro
  • Code
  • Assignments

Matrix Exponentiation and Dynamic Programming #

  • Binary Exponentiation
  • Modular Exponentiation
  • Fast Multiplication
  • Matrix Exponentiation
  • Matrix Exponentiation Code
  • Fibosum (spoj) first approach
  • Fibosum (spoj) second approach
  • Assignments

Game Theory and Dynamic Programming #

  • Combinatorial Games
  • Game Theory Problems using DP
  • Mesere Rule
  • Examples
  • N/P Positions
  • Chessboard Game
  • Stone Division
  • Assignments

Dynammic Programming with Advance Data Structures #

  • Intro
  • Segment Trees - SUPW with K
  • SUPW with K (code)
  • Fenwick Trees - Longest Increasing Subsequence (nlogn)
  • LIS(code)
  • Using Sparse Matrix

Tips and tricks #

  • Forward vs Backward DP approaches
  • Same state and multiple recurrence relations
  • Recover the best solutions
  • Super Duper Memory and Time Optimisation - Subset Sum

Challenging DP Problems #

  • Assignments

Additional Problem to Try! #

  • Assignments

At Coder Dynammic Programming Educational Contest (A-Z) #

  • Warning
  • Frogs - 1
  • Forgs - 2
  • Vacation
  • Knapsack - 1
  • Knapsack - 2
  • LCS
  • LCS(code)
  • Longest Path
  • Longest Path (code)
  • Grid 1
  • Grid 1 (code)
  • Coins
  • Coins (code)
  • Sushi
  • Sushi (code)
  • Stones
  • Deque (First solution)
  • Deque (Second Solution)
  • Candies
  • Candies(code)
  • Slimes
  • Slimes (code)
  • Matching
  • Matching continues
  • Matching (code)
  • Independent Set
  • Independent Set(code)
  • Flowers
  • Flowers using Segment Tree
  • Flowers(code)
  • Walk
  • Walk(code)
  • Digit Sum
  • Digit Sum (code)
  • Permutation
  • Permutation Brute Force
  • Permutation (code)
  • Grouping
  • Grouping (code)
↑