Dynamic Programming

Dynamic Programming

 Questions and related way of solving DP questions 

Interval DP:

• Burst Balloons  
• Matrix Multiplication 
• Optimal Binary Search Tree
• Longest Palindromic Subsequence
• Palindromic Partition: find min no of splits such that each subpart is palindrome
• Word Break/ Word Split in Dictionary or not
• Game Strategy Optimal Pick (2 Players)

Knapsack DP:

• 0/1 Knapsack  
• Coin change 
• Subset Sum 
• Cutting Rod 

Single Array DP:

• Longest Increasing Subsequence 
• Kadane's Algorithm 
• Maximum Sum subarray
• Maximum Sum Rectangular Subarray (Level 2 Kadane)
• Stock buy sell any number of transactions

2-D Array DP 

• Longest Common Subsequence vs Longest Common String 
• Minimum Edit Distance 

Min-max Problem 

• Egg Dropping Problem 
• Stock Buy Sell at most k transactions 
• Stock Buy sell at most 1 transaction