5.1 DP Strategies

• Range DP
  • $dp[l][r]=$ minimum cost to make substring $s[l..r]$ a palindrom
  • Usually $dp[l][r]=\min (dp[l+1][r],dp[l][r-1],dp[l+1][r-1]+\text{ cost})$
• All-possible-splits DP
  • Matrix chain mult.: $\text{DP}[i][j]={\min }_{i\le k<j}\left(\underset{\text{left matrix}}{\underbrace{\text{DP}[i][k]}}+\underset{\text{right matrix}}{\underbrace{\text{DP}[k+1][j]}}+\underset{\text{combining}}{\underbrace{p_{i-1}\cdot p_k\cdot p_j}}\right)$
  • Try all possible splits and chose cheapest one
• Sliding window
  • Idea: Extend window until no more possible. Then either reset window or pull from left.
• Prefix sum
  • Precompute the sum up until element
  • Return $dp[end]-dp[start]$