Arithmetic Progression with Range

题目：
给一个数组，{7, 4, 2, 2},判断给定区间是不是等差数列。例如{{2, 3}, {1, 4}, {3, 4}}, 输出结果就是Y, N, Y.

解题思路：
这道题就是用动态规划的解法来做，建立一个二维的矩阵来储存相应的index范围的boolean值。

代码：

public class ArithmeticProgressionwithRange {

    /*    *    *   给一个数组，{7, 4, 2, 2},判断给定区间是不是等差数列。例如{{{2, 3}, {1, 3}, {3, 4}, {1, 4}}}, 输出结果就是Y, N, Y, N.         0, 1, 2, 3        [7, 4, 2, 2]
      // dynamic programming        0  1  2  3      0 y  y  n  n      1    y  y  n      2       y  y      3          y
       {7, 4, 1, 0}        0  1  2  3      0 y  y  y  n      1    y  y  n      2       y  y      3          y      given ranges of {{2, 3}, {1, 3}, {3, 4}, {1, 4}} we should have ->Y, Y, Y, N    * */
    public static void main(String[] args){
        ArithmeticProgressionwithRange arithmeticProgressionwithRange = new ArithmeticProgressionwithRange();
        int[] nums1 = {7, 4, 2, 2};
        int[] nums2 = {7, 4, 1, 0};
        List<List<Integer>> ranges = new ArrayList<>();
        List<Integer> l1 = new ArrayList();
        List<Integer> l2 = new ArrayList();
        List<Integer> l3 = new ArrayList();
        List<Integer> l4 = new ArrayList();
        l1.add(2);
        l1.add(3);
        l2.add(1);
        l2.add(3);
        l3.add(3);
        l3.add(4);
        l4.add(1);
        l4.add(4);
        ranges.add(l1);
        ranges.add(l2);
        ranges.add(l3);
        ranges.add(l4);
        List<Boolean> rst1 = arithmeticProgressionwithRange.checkRange(nums1, ranges);
        List<Boolean> rst2 = arithmeticProgressionwithRange.checkRange(nums2, ranges);
        System.out.println(rst1);
        System.out.println(rst2);
    }

    public List<Boolean> checkRange(int[] nums, List<List<Integer>> ranges){
        // assuming that the ranges and the nums are both null and their sizes are larger than 0.        List<Boolean> rst = new ArrayList<>();
        if(nums.length == 1){
            // assuming that the ranges are always within that range of nums' start index and end index            rst.add(true);
            return rst;
        }
        int len = nums.length;
        // start building our 2d boolean array here        boolean[][] dp = new boolean[len][len];
        for(int i = 0; i <= len - 1; i++){
            for(int j = i; j <= len - 1; j++){
                if(i == j || j - i == 1){
                    dp[i][j] = true;
                }
                // if (j - 2) - (j - 1) == (j - 1) - (j)                else if(dp[i][j - 1] && (nums[j - 2] - nums[j - 1] == nums[j - 1] - nums[j])){
                    dp[i][j] = true;
                }
                else{
                    dp[i][j] = false;
                }
            }
        }
        for(int i = 0; i <= ranges.size() - 1; i++){
            boolean temp = getBooleanResult(dp, ranges.get(i));
            rst.add(temp);
        }
        return rst;
    }

    private boolean getBooleanResult(boolean[][] dp, List<Integer> range) {
        // assuming that the range is always valid        int left = range.get(0);
        int right = range.get(1);
        boolean rst = dp[left - 1][right - 1];
        return rst;
    }


}