Readme

3699.Number-of-ZigZag-Arrays-I

考虑到数据量，不难想到用基础的DP来解决。令up[i][x]表示第i个元素为x、且最后一段是上升的合法序列的数列。同理可以定义down[i][x]。其中x的范围是[1,m]，且m=r-l+1;

对于up[i][x]的状态转移，很明显取决于序列里的前一个元素。根据题意，以第i-1个元素结尾的序列的最后一段必须是下降的，故第i-1个元素必须是大于x的。所有有

up[i][x] = sum(down[i-1][y]) for y=x+1,...,m

同理有

down[i][x] = sum(up[i-1][y]) for y=1,2,...,x-1

最终返回sum(up[i][x]+down[i][x]) for x=1,2,...,m.

本题的时间复杂度只取决于最外的两层循环N*M. 当遍历x时，我们可以记录donw[i][y]的前缀和，就可以高效地计算up[i][x].