Skip to main content

Advanced DP Patterns

Complex dynamic programming patterns that require deeper understanding and more sophisticated state management.

Knapsack problems​

  • 0/1 Knapsack: Each item can be used at most once
  • Unbounded Knapsack: Each item can be used multiple times
  • Fractional Knapsack: Items can be partially used (greedy approach)
  • Multiple Constraints: Knapsack with multiple capacity constraints

Edit distance​

  • Problem: Minimum operations to transform one string into another
  • Operations: Insert, delete, replace characters
  • DP State: dp[i][j] = edit distance between first i chars of string1 and first j chars of string2
  • Recurrence: dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+cost)

Longest increasing subsequence​

  • Problem: Length of longest subsequence that is strictly increasing
  • DP State: dp[i] = length of LIS ending at index i
  • Recurrence: dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]
  • Optimization: Binary search approach for O(n log n) solution

Matrix chain multiplication​

  • Problem: Minimum number of scalar multiplications for matrix chain
  • DP State: dp[i][j] = minimum cost to multiply matrices from i to j
  • Recurrence: dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost[i][k][j]) for k in [i, j-1]
  • Base Case: dp[i][i] = 0

Palindrome problems​

  • Longest Palindromic Subsequence: Length of longest palindromic subsequence
  • Longest Palindromic Substring: Length of longest palindromic substring
  • Palindrome Partitioning: Minimum cuts to partition string into palindromes
  • Count Palindromic Substrings: Count all palindromic substrings