思路

最后只计算总数，所以l、r本身没有意义，rg = r-l才有意义，我们可以设元素范围为[0, rg]。
按照题意，只要确定了前两个元素是递增还是递减，后面的元素增减顺序就确定了，而且两者的总数一定是一样的。
可以用递推/动规作答，确定了增减性和前一个元素的可能性，就能计算当前元素的可能性。


递增时dp[i][j] = sum(dp[i - 1][1..j - 1])
递减时dp[i][j] = sum(dp[i - 1][j + 1..rg])

代码
class Solution {
    private static final int MOD = 1000000007;
    public int zigZagArrays(int n, int l, int r) {
        int rg = r - l + 1;
        int[] dp = n...