[数据结构与算法]动态规划+背包思路计算所有组合方案

package com.patience.interview.algorithms;

/**
 * day 4
 * @author Green.Gee
 * @date 2022/3/9 14:34
 * @email green.gee.lu@gmail.com
 */
public class SolveQ4 {

    /**
     * N 个 位置中 三个 ,并且 距离 最远 不能大于 D
     * 给出一组数列 nums
     *  寻找所有可选方案
     *  可能溢出 99997867 取模
     *  ----------
     *  动态规划 + 背包
     */
    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;
    }
}