优化DP
前缀和优化
leetcode 3699
寻找子问题：如果长度为n的序列此时是递增的，它的前一个状态必须是递减的且位置n(index从1开始)的数必须大于位置为n-1的数。这时我们发现需要两个维度和两个数组定义状态，一个维度表示当前序列长度i，另一个维度表示当前结尾的数字j。一个数组dp1表示当前状态是递增时的方案数，另一个数组dp2表示当前状态是递减时的方案数。两个数组的计算方式完全对称。为简化计算，[l, r]区间可以对应到[0, r - l]。
dp1[i][j] = dp2[i - 1][0] + dp2[i - 1][1] + ... + dp2[i - 2][j - 1]
dp2[i][j] = dp1[i - 1][j + 1] + dp1[i - 1][j + 2] + ... + dp1[i - 1][r - l]
如果直接计算，时间复杂度O(n^3)，因为要枚举i、j和i-1位置可选的数字k。观察到前一项的计算是累加和的形式，可用前缀和优化到O(1)，整体时间复杂度O(n^2)
此题数据应该没有用python测试，直接写会超时。
注意到每一项递推只和前一项有关，因此可以用滚动数组优化；前缀和用itertools库里的accumulate方法加速计算