Dynamic Programming

Dynamic programming is beautiful because we usually want to solve problem backwards. There is a 5 mins Ted talk discussing Working backward to solve problems

Must Know

3 Levels of a DP problem

• Can this be done? [Or] What is the minimum cost of accomplishing this?
• How many solutions are there?
• Enumerate all the solutions?

Classical (Video)

• Fibonacci
  • Climbing Stairs
  • Decode Ways
  • Decode Ways II
• Maximum Sum Subsequence Non-Adjacent
  • House Robber
  • Numbers Without Consecutive 1s in Binary Representation
  • Non-negative Integers without Consecutive Ones
• Knapsack Problem
  • 0/1 Knapsack Problem
    • Subset Sum
    • Partition Equal Subset Sum
    • [Subset Sum (Contains Negative Numbers)]
    • Target Sum
  • Coin Changing
    • Coin Changing Number of ways
    • Coin Chaning Minimum Coins
  • Frog Jump
    • Freedom Trail
  • Combination Sum IV
  • Perfect Squares
  • Integer Break
• Matrix Chain Mutiplication
  • Burst Balloon
  • Remove Boxes (Hard) (sub-problem is not self contained)
  • Counting Boolean Parenthesizations
  • Strange Printer
  • Floyd-Warshall Algorithm
  • Palindrome Partition
  • Longest Valid Parentheses
  • Cutting Rod
  • Word Break
  • Concatenated Words
• Longest Increasing Subsequence
  • Longest Bitonic Subsequence
  • 376. Wiggle Subsequence
  • Number of Longest Increasing Subsequence
  • Maximum Sum Increasing Subsequence
  • Weighted Job Scheduling
  • Maximum Length of Chain of Pairs
  • Largest Divisible Subset
  • Russian Doll Envelopes
  • Box Stacking
  • Arithmetic Slices II - Subsequence
  • Building Bridges
• Longest Common Substring
  • Longest Palindromic Substring
  • Longest Common Subsequence
  • Distinct Subsequences
  • Longest Palindromic Subsequence
  • Palindrome Partition
  • Longest Repeated Subsequence
• Unique Path
  • Minimum Cost Path
  • Minimum Jump to Reach End
  • Out of Boundary Paths
  • Knight Probability in Chessboard
  • Triangle
  • Dungeon Game
• Minimum Edit Distance
  • Wild Card Matching
  • Regular Expression Matching
  • String Interleaving
• Largest Sum Contiguous Subarray
  • Maxium Sum Rectangular Submatrix in Matrix
  • Maximum sum subarray having sum less than k (very interesting)
  • Max Sum of Rectangle No Larger Than K
• Maximum Sub Square Matrix
• Sum Query in 2D immutable Array
• Text Justification
• Maximum Subsquare With Sides as X
  • Maximum Rectangular Area in Histogram
  • Maximum Size Rectangle of All 1's
• Egg Dropping
  • Buy/Sell Stock With K Transactions
  • Split Array Largest Sum
• Optimal Strategy Game Pick from Ends of Array
  • Can I Win
• Optimal Binary Search Tree
  • Count Number of Binary Search Tree Possible Given N keys
  • Count Number of Binary Tree Possible GIven Preorder Sequence Length

Tricks

Porblem set

EPI

CCTI

Leetcode

• 322. Coin Change
• 518. Coin Change 2
• 300. Longest Increasing Subsequence
• 673. Number of Longest Increasing Subsequence
• 516. Longest Palindromic Subsequence
• 139. Word Break
• 416. Partition Equal Subset Sum
• 53. Maximum Subarray
• 64. Minimum Path Sum
• 55. Jump Game
• 188. Best Time to Buy and Sell Stock IV
• 650. 2 Keys Keyboard
• 647. Palindromic Substrings
• 646. Maxium Length of Pair Chain
• 576. Out of Boundary Paths
• 688. Knight Probability in Chessboard
• 44. Wildcard Matching
• 467. Unique Substrings in Wraparound String
• 368. Largest Divisible Subset
• 377. Combination Sum IV
• 494. Target Sum
• 63. Unique Paths II
• 304. Range Sum Query 2D - Immutable
• 221. Maximal Square
• 70. Climbing Stairs
• 338. Counting Bits
• 279. Perfect Squares
• 120. Triangle
• 343. Integer Break
• 198. House Robber
• 213. House Robber II
• 256. Paint House
• 361. Bomb Enemy
• 96. Unique Binary Search Trees
• 95. Unique Binary Search Trees II
• 638. Shopping Offers
• 464. Can I Win
• 120. Triangle
• 712. Minimum ASCII Delete Sum for Two Strings
• 474. Ones and Zeroes
• 152. Maximum Product Subarray
• 486. Predict the Winner

Hard

• 72. Edit Distance
• 312. Burst Balloons
• 403. Frog Jump
• 10. Regular Expression Matching
• 689. Maximum Sum of 3 Non-Overlapping Subarrays
• 664. Strange Printer
• 115. Distinct Subsequences
• 32. Longest Valid Parentheses
• 85. Maximal Rectangle
• 97. Interleaving String
• 132. Palindrome Partitioning II
• 174. Dungeon Game
• 354. Russian Doll Envelopes
• 363. Max Sum of Rectangle No Larger Than K
• 410. Split Array Largest Sum
• 514. Freedom Trail
• 446. Arithmetic Slices II - Subsequence
• 472. Concatenated Words
• 546. Remove Boxes
• 91. Decode Ways
• 639. Decode Ways II
• 68. Text Justification

GeeksforGeeks

• Minimum Ways of Changing Coins
• Weighted Job Scheduling (Largest Increasing Subsequence)
• Egg Dropping Problem
• Cutting Rod
• Counting Boolean Parenthesization Problem
• Maxium Sum Rectangular Submatrix in Matrix
• Minimum Partition
• Longest Path in Matrix
• Optimal Strategy for a Game
• Boolean Parenthesization
• Maximum Product Cutting Rod
• Dice Throw Problem