Dynamic Programming

Topics

• Dynamic Programming Introduction

• 0/1 Knapsack

• Unbounded Knapsack

• Longest Common Subsequence

• Edit Distance

• Matrix Chain Multiplication

• Longest Increasing Subsequence and Kadane's Algorithm

• DP On 2D Grid

• Dynamic Programming Introduction

  • What is Dynamic Programming?

• 0/1 Knapsack

  • Types of Knapsack

  • 0/1 Knapsack

  • Subset Sum

  • Equal Sum

  • Count of Subset Sum with a Given Sum

  • Minimum Subset Sum Difference

  • Count the number of subset with a given difference

  • Target Sum

  • Subset Sum Using Exactly K numbers from N numbers

  • From an array of N elements How many Subset Sum using P elements will be Divided by M

• Unbounded Knapsack

  • Introduction to Unbounded Knapsack

  • Rod Cutting Problem

  • Coin Change Maximum Number Of Ways

  • Coin Change Minimum Number of Coins

  • Each Coin can be used up to K times Maximum Ways to make a Value

• Longest Common Subsequence

  • Longest Common Subsequence Introduction

  • Longest Common Subsequence

  • Lexicographically Smaller LCS

  • Longest Common Substring

  • Shortest Common Supersequence

  • Count the Number of Shortest Common Supersequence

  • Minimum Number of Insertion and Deletion to Convert String X to String Y

  • Longest Palindromic Subsequence

  • Minimum Number of Deletion in a String to make it Palindrome

  • Minimum Number of Insertion to make a string Palindrome

  • Longest Repeating Subsequence

  • Sequence Pattern Matching

  • Find Maximum K x LCS(C,D) - L(C) - L(D) Where C,D are Substrings of A,B

  
  
  

• Edit Distance

  • Introduction to Edit Distance

  • Minimum Edit Distance

  
  
  

• Matrix Chain Multiplication

  • General MCM format and Identification

  • Matrix Chain Multiplication

  • Palindrome Partioning

  • Boolean Parenthesization

  • Scrambled String

  • Egg Dropping Problem

• Longest Increasing Subsequence and Kadane's Algorithm

  • Longest Increasing Subsequence

  • Longest Increasing Even or Odd Subsequence

  • Longest Increasing Alternating Subsequence

  • Box Stacking Problem

  • Kadane Algorithm

  • Kadane Algorithm Range

  
  
  

• DP On 2D Grid

  • Unique Paths in 2D grid without Obstacles

  • Unique Paths in 2D grid with Obstacles

  • Minimum Cost Path

  • Maximal Square

  • Maximal Rectangle