令人谔谔的题。被张老师评价为“第一次看到很难独立想出来”的题。容易想到状态 dp_{i,j,k} 表示第 i 步在草丛 j 并且方向为 k 的方案数。发现会算重并且很难去重。但是呢在评讲之前还是一直在想怎么去重，没有往状态设计方面想得很深。
事实上这道题考察的就是对于状态的设计。也可以称这种 DP 方式为 “插入DP”，看起来就像是区间 DP 的一种特殊情况。可以发现当我们画出一个步数-路径图像，合法的方案一定是一个 多重 M 形。对于这种图像有一个特征，就是我们可以找到其中的最高点并将其划分为两个不同的 多重 M 形（我们把单点也看做一个 多重 M 形）。那么我们就可以反过来，每次操作时插入一个最大值并合并两个 多重 M 形。那么状态就很显然了，dp_{i,j} 表示当前插入了数 i 并且有 j 个 多重 M 形 的方案数，转移可以开一个新的单点 多重 M 形，也可以合并两个 多重 M 形，对于 s 和 t 多讨论一点，最后输出 dp_{n,1} 即可。