动态规划+背包思路计算所有组合方案

package com.patience.interview.algorithms;


public class SolveQ4 {

    
    public static void main(String[] args) {
        final long C = 99997867;
        int N = 5;// 个数
        int D = 5;// 最远距离
        int[] nums = new int[]{1,2,3,4,5};// 所有位置点
        long count = 0;
        for (int i = 0,j = 0; i < N; i++) {
            while(i >= 2 && (nums[i] - nums[j]) > D)
                j++;
            count += cal(i - j);
        }
        count = count % C;
        System.err.println(count);
    }
    // n (n - 1) / 2
    public static long cal(long nums){
        return nums * (nums - 1) / 2;
    }
}