Dynamic programming problems lecture

THESE ARE FOR NOW

• Longest Common Subsequence | Introduction & LCS Length
• Longest Common Subsequence | Finding all LCS
• Longest Common Substring problem
• Longest Palindromic Subsequence using Dynamic Programming
• Longest Repeated Subsequence Problem
• Implement Diff Utility
• Shortest Common Supersequence | Introduction & SCS Length
• Shortest Common Supersequence | Finding all SCS
• Longest Increasing Subsequence using Dynamic Programming
• Longest Bitonic Subsequence
• Increasing Subsequence with Maximum Sum
• The Levenshtein distance (Edit distance) problem
• Find size of largest square sub-matrix of 1’s present in given binary matrix
• Matrix Chain Multiplication using Dynamic Programming
• Find the minimum cost to reach last cell of the matrix from its first cell
• Find longest sequence formed by adjacent numbers in the matrix
• Count number of paths in a matrix with given cost to reach destination cell
• 0–1 Knapsack problem
• Maximize the Value of an Expression
• Partition problem | Dynamic Programming Solution
• Subset Sum Problem
• Minimum Sum Partition Problem
• Find all N-digit binary strings without any consecutive 1’s
• Rod Cutting Problem
• Maximum Product Rod Cutting
• Coin change-making problem (unlimited supply of coins)
• Coin Change Problem (Total number of ways to get the denomination of coins)
• Longest Alternating Subsequence Problem
• Count number of times a pattern appears in given string as a subsequence
• Collect maximum points in a matrix by satisfying given constraints
• Count total possible combinations of N-digit numbers in a mobile keypad
• Find Optimal Cost to Construct Binary Search Tree
• Word Break Problem | Dynamic Programming
• Word Break Problem | Using Trie Data Structure
• Total possible solutions to linear equation of k variables
• Wildcard Pattern Matching
• Find Probability that a Person is Alive after Taking N steps on an Island
• Calculate sum of all elements in a sub-matrix in constant time
• Find Maximum Sum Submatrix in a given matrix
• Find Maximum Sum Submatrix present in a given matrix
• Find maximum sum of subsequence with no adjacent elements
• Maximum Subarray Problem (Kadane’s algorithm)
• Single-Source Shortest Paths — Bellman Ford Algorithm
• All-Pairs Shortest Paths — Floyd Warshall Algorithm
• Pots of Gold Game using Dynamic Programming
• Find minimum cuts needed for palindromic partition of a string
• Maximum Length Snake Sequence
• 3-Partition Problem
• Calculate size of the largest plus of 1’s in binary matrix
• Check if given string is interleaving of two other given strings
• Link to a Quora post, where people posted a lot of DP problems

• TO DO

  • INUMBER - Spoj problem, digit dp + bfs + backtrack
  • LEXBRAC - Spoj problem, digit dp + big numbers
  • LSORT - Spoj problem, can be recursively solved or iteratively, but some tricky computations I am not able to think at the moment and that is because i wanted just to code, practice some simpler problems, to stay in touch
  • MINUS - Spoj problem, not so hard, it is basically some kind of knapsack, but you need to get there first(some ad hoc)