过河

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param l int整型
     * @param s int整型
     * @param t int整型
     * @param nums int整型ArrayList
     * @return int整型
     */
    public int crossRiver (int l, int s, int t, ArrayList<Integer> nums) {
        // write code here
        if (l <= t) {
            return 0;
        }

        int result = 0;

        // 1 只能跳跃一种距离
        if (s == t) {
            for (int stone : nums) {
                if (stone % t == 0 && stone <= l) {
                    result++;
                }
            }

            return result;
        }

        // 2 可以跳跃多种距离
        // 离散化处理 <- l很大 m很小
        final int PERIOD = t * (t - 1);
        Collections.sort(nums);
        int m = nums.size();
        int[] stones = new int[m];
        int distance;
        HashSet<Integer> stoneSet = new HashSet<>();
        for (int i = 0; i < m; i++) {
            if (i == 0) {
                distance = nums.get(i);
                stones[i] = distance % PERIOD;
            } else {
                distance = nums.get(i) - nums.get(i - 1);
                stones[i] = stones[i - 1] + distance % PERIOD;
            }
            stoneSet.add(stones[i]);
        }
        distance = l - stones[m - 1];
        l = stones[m - 1] + distance % PERIOD;

        int[] dp = new int[l + t];
        Arrays.fill(dp, Integer.MAX_VALUE >> 1);

        // init
        for (int i = s; i <= t; i++) {
            if (stoneSet.contains(i)) {
                dp[i] = 1;
            } else {
                dp[i] = 0;
            }
        }

        for (int i = t + 1; i < l + t; i++) {
            for (int j = s; j <= t; j++) {
                if (dp[i - j] != Integer.MAX_VALUE >> 1) {
                    if (stoneSet.contains(i)) {
                        dp[i] = Math.min(dp[i], dp[i - j] + 1);
                    } else {
                        dp[i] = Math.min(dp[i], dp[i - j]);
                    }
                }
            }
        }

        result = Integer.MAX_VALUE;
        for (int i = l; i < l + t; i++) {
            result = Math.min(result, dp[i]);
        }

        return result;
    }
}