> For the complete documentation index, see [llms.txt](https://osh.fducslg.com/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://osh.fducslg.com/notes/leetcode/dynamic-programming.md).

# Dynamic Programming

[42. 接雨水](https://leetcode.cn/problems/trapping-rain-water/)

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

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

第二遍同理。

***

[32. 最长有效括号](https://leetcode.cn/problems/longest-valid-parentheses/description/)

**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]`对应不了有效序列。