DP patterns— [Notes]

· 0/1 Knapsack
· Unbounded knapsack
· Fibonacci
· LCS — Longest common subsequence
∘ Longest Palindromic Subsequence
· LIS — Longest increasing subsequence
· Kadane’s algorithms
· Matrix Chain Multiplication
· Rod cutting
· DP on trees
· DP with bit-masking
· Digit DP
· DP on graphs
· Sum over Subsets
· DP on Grid
· Best time to buy and sell stocks
· Unique google questions
· TODO/Sort

0/1 Knapsack

• 0/1 knapsack → Code
• Subset sum → Code
• Equal sum partition / 416. Partition Equal Subset Sum → Code
• Count of subset sum → Code
• Minimum subset sum diff (with all positive numbers) → Code
• Count the number of subset with a given difference → Code
• 494. Target Sums (Numbers are +ves, Target can be +ve/-ve) → Code
• 🔴[TODO] 2035. Partition Array Into Two Arrays to Minimize Sum Difference (with negative numbers) → Code

Note: This is a hard problem and not a straightforward DP Problem. Dependent problem — Men in Middle. Refer below videos

▶ https://youtu.be/JUFHwaZjO_M

▶ https://youtu.be/UoKGRTIZvM0

Unbounded knapsack

• Rod cutting (Max Cost)→ Code
• 1547. Minimum Cost to Cut a Stick → Code
• Coin change I → Code
• 518. Coin Change II (number of combinations that make up that amount) → Code
• 🔴[TODO] Maximum Ribbon Cut → Code

Fibonacci

LCS — Longest common subsequence

• Longest common subsequence (LCS) → Code
• 😵🤩[Revise — Recursive approach] Longest common substring → Code
• Print LCS → Code
• Length of Shortest common super-sequence → Code
• Print Shortest common super-sequence → Code
• Minimum Number of Insertion and Deletion to convert String a to String b → Code
• 🔴[TODO] Edit Distance

Longest Palindromic Subsequence

• Longest Palindromic Subsequence → Code
• Minimum number of deletion in a string to make it a palindrome → Code
• Print shortest common Supersequence → Code
• Length of Longest repeating subsequence → Code
• Sequence Pattern Matching → Code
• Minimum number of insertion in a string to make it a palindrome → Code

LIS — Longest increasing subsequence

Kadane’s algorithms

Matrix Chain Multiplication

• MCM → Code
• 🔴[TODO] MCM Bottom Up
• Print MCM
• Palindrome Partitioning → Recursive + Memo Code
• 🔴[TODO] Palindrome Partitioning → Bottom Up code
• Evaluate Expression to True Boolean Parenthesization Recursive → Code

Rod cutting

DP on trees

DP with bit-masking

• https://www.geeksforgeeks.org/bitmasking-and-dynamic-programming-set-1-count-ways-to-assign-unique-cap-to-every-person/
• https://www.geeksforgeeks.org/bitmasking-dynamic-programming-set-2-tsp/

Digit DP

• https://www.geeksforgeeks.org/digit-dp-introduction/

DP on graphs

Sum over Subsets

• https://www.geeksforgeeks.org/sum-subsets-dynamic-programming/

DP on Grid

Best time to buy and sell stocks

• https://github.com/dilipkumar2k6/dynamic-programming#:~:text=Best%20time%20to%20buy%20and%20sell%20stocks

Unique google questions

#1

#2

TODO/Sort

DYNAMIC PROGRAMMING PATTERNS