思路

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

• 递增时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 = new int[rg];
        Arrays.fill(dp, 1);
        long lastSum = rg;
        for (int i = 1; i < n; i++) {
            int[] curr = new int[rg];
            long lastSumTmp = ((i & 1) == 0) ? lastSum : 0;
            long currSum = 0;
            for (int j = 0; j < rg; j++) {
                if ((i & 1) == 0) {
                    lastSumTmp -= dp[j];
                    if (lastSumTmp < 0) {
                        lastSumTmp += MOD;
                    }
                    curr[j] = (int) (lastSumTmp % MOD);
                } else {
                    curr[j] = (int) (lastSumTmp % MOD);
                    lastSumTmp += dp[j];
                }
                currSum += curr[j];
            }
            dp = curr;
            lastSum = currSum;
        }
        return (int) (lastSum * 2 % 1000000007);
    }
}