题目简述
一排格子，每个格子上有“L”或“R”，表示向左或向右跳到任意位置。问从任意位置出发跳完所有的格子在第\(i\)格子结束的方案数。答案对 \(10^9 + 7\) 取模。
分析 & 性质
- 考虑一个选取方案，取的位置序列为排列
- 与相对位置有关的信息可以考虑插入顺序
最终思路
使用连续段dp的方法（从小到大插入）：
- 插入到段的两端，可知“L”只能插到段左侧，“R”插到右侧
- 发现连续段关于插入时刻为单谷，“R”在谷，“L”在连接处（合并后的峰）
可知dp柿子：
\(dp[i][j] \times (j - 1) \rightarrow dp[i + 1][j - 1]\ (ch_i == L)\)
\(dp[i][j] \times (j + 1) \rightarrow dp[i+ 1][j + 1]\ (ch_i == R)\)
\(dp[i][j] \times j \rightarrow dp[i + 1][j]\)
对于最终答案，将对应位置放到操作序列末端，然后将反着dp的峰与正着dp的谷拼上。
- 对于接口处下半部分为谷右侧“R”， 上半部分为峰左侧为“R”，可连接，其他同理。