Dynamic Programming

42. 接雨水

核心Observation：每个index对应可存的雨水量 = min(向左第一个山头的高度，向右第一个山头的高度)

于是，我们要扫两遍序列，第一遍找出每个index对应的向左第一个山头的高度。遍历过程中，若序列单调增，则不断更新山头高度；若序列单调减，则沿用前一个index对应的向左第一个山头的高度。这里就是DP思想的运用，即怎样由 arr[index-1] 推得 arr[index]。

第二遍同理。

---

32. 最长有效括号

DP规约：我们考虑每个index作为有效区间的右界时，其对应的有效区间的长度，得到valid_len[n]。最后我们只需要找到max(valid_len)即可。

规律总结：对于序列问题，我们可以考虑每个index的结果，得到与原序列伴生的intermediate[n]，然后我们只需处理伴生序列。如上一题是求和，本题是求最大。

在这样的规约下，(显然不能作为有效序列的结尾，因此我们要考虑)对应的有效序列的长度。考虑到DP的递推性，我们如何由dp[0:i]生成dp[i]？

1. 如果dp[i-1] == '('，那么dp[i-1:i+1]就是一个有效的括号对，可以append到dp[i-2]对应的有效序列上。

2. 如果dp[i-1] == ')'，那么dp[i]能不能对应一个能够包含s1的新序列，记为s2， 的结尾？我们需要看看**dp[i-1]对应的有效序列s1的起始点**的前一位是否是(。

   如果是(，dp[i]对应的序列长度比dp[i-1]对应的序列长2（s1首尾被包了一个括号对）。此外，我们还需要把s2 append 到 dp[i-1]对应的有效序列s1的起始点前一位（dp[i−dp[i−1]−2]）对应的有效序列上。

   如果不可以的话，那么dp[i]对应不了有效序列。