区间型动态规划

516. Longest Palindromic Subsequence

给一个字符串找到最长的回文子串

• 状态：dp[i][j]表示S[i..j]的最长回文子串的长度

  $$dp[i][j] = max(dp[i+1][j], dp[i][j-1], dp[i+1][j-1]+2 | s[i] == s[j])$$

• 递归公式不再是从小的方向往大的方向传，所以计算顺序要改变！按照长度。

312. Burst Balloons

消去型动态规划，给n个气球，扎破气球的得分a[left]*a[i]*a[right],求获得的最多金币数？

• 从最后一步出发！！！

87. Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.