代码理解不了，初学者不太懂

Question

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。

题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。
1<=L<=10^9,
1<=S<=T<=10,
1<=M<=100

输入描述:
第一行有一个正整数L ，表示独木桥的长度。
第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数
第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。
所有相邻的整数之间用一个空格隔开。

输出描述:
只包括一个整数，表示青蛙过河最少需要踩到的石子数。
示例1
输入
10
2 3 5
2 3 5 6 7
输出
2

https://www.nowcoder.com/questionTerminal/35ddfeb4e34f410bb9035682463a382f?answerType=1&f=discussion

 
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.Arrays;
 
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
 
    // 注意 hasNext 和 hasNextLine 的区别
    while (in.hasNext()) { // 注意 while 处理多个 case
        int n = in.nextInt();
        int s = in.nextInt();
        int t = in.nextInt();
        int m = in.nextInt();
        ArrayList<Integer> stones = new ArrayList();
        for(int i=0;i<m;i++) {
            stones.add(in.nextInt());
        }
        Collections.sort(stones);
 
        if(s==t) {
            singleJudge(s,stones);
        } else {
            rangeJudge(s,t,n,stones);
        }
    }
}
 
public static void singleJudge(int s,ArrayList<Integer> stones) {
    int stoneNumber = 0;
    for(int i=0;i<stones.size();i++) {
        if(stones.get(i)%s == 0) {
            stoneNumber++;
        }
    }
    System.out.println(stoneNumber);
}
 
public static void rangeJudge(int s,int t,int n,ArrayList<Integer> stones) {
    int compressLen = compressBridgeLength(stones,n,t);
    int[] dp = new int[compressLen+t+1];
    Arrays.fill(dp,10000);
    dp[0] = 0;
    int stoneNumber = 10000;
    int maxStep = 0;
    for(int i=s;i<=compressLen+t;i++) {
        maxStep = Math.max(maxStep,i);
        for(int j=s;j<=t;j++) {
            if(i>=j) {
                dp[i] = Math.min(dp[i],dp[i-j]);
            }
        }
        if(stones.contains(i)) {
            dp[i] +=1;
        }
    }
 
    for(int i=compressLen;i<=maxStep;i++) {
        stoneNumber = Math.min(dp[i],stoneNumber);
    }
    System.out.println(stoneNumber);
}
 
public static int compressBridgeLength(ArrayList<Integer> stones,int n,int t) {
    for(int i=1;i<stones.size();i++) {
        int distance = stones.get(i) - stones.get(i-1);
        stones.set(i,stones.get(i-1) + distance%90);
    }
    n = (n - stones.get(stones.size()-1))%90 + stones.get(stones.size()-1);
    return n;
}
}
 

Answer 1

给你加了些注释

题解
先不考虑开不下数组的问题

如果我们用f[i]表示走到i这个位置的最小的踩石子的次数话

i这个位置没有石头：f[i]=min(f[i],f[k])

i这个位置是石头：f[i]=min(f[i],f[k]+1)

(k是上一步的位置， [公式] )

现在我们来解决桥太长了数组开不了的问题，我首先仔细看数据范围，相对于桥长度L，石头个数和青蛙跳跃范围S，T都是很小的，也就是说总是存在一些石头离得非常远，从前一个石头到这个石头需要跳很多步才能到达，而只要S和T不等，那么在这漫长的跳跃中我们总可以调整步幅使得踩不到这颗石子。换句话说，只要S和T不等当两个石子之间的距离超过了一定范围之后，任意距离都是可以到达的，这个时候两个离得很远的石头之间的距离就不重要了，那么现在我们就来考虑这个距离是多少：

（其实如果是比赛的时候，你其实可以根据时空限制直接估算这个值，能卡着时空过就行了）

我们先看例子，当S=3，T=4的时候那些长度是可以到达的：

3 、4、 6=3+3、 7=3+4、 8=4+4、 9=3+3+3、 10=3+3+4、 11=3+4+4、 12=4+4+4/3+3+3+3、13、14、15……

S=5，T=6时:

5、6、10=5+5、11=5+6、12=6+6、15=5+5+5、16=5+5+6、17=5+6+6、18=6+6+6、20=5+5+5+5、21=5+5+5+6、22=5+5+6+6、23=5+6+6+6、24=6+6+6+6、25=5+5+5+5+5、26=5+5+5+5+6、27=5+5+5+6+6、28=5+5+6+6+6、29=5+6+6+6+6、30=6+6+6+6+6/5+5+5+5+5+5……

我们发现，当长度超过 [公式] 之后，这个长度会有至少两种跳的方式（T个S相加和S个T相加），之后我们可以在每一步比都在较小的那种方法（T个S相加）的基础上将某些步的长度变大，然后就可以跳出更长的长度，也就是说 [公式] 及其之前的所有长度都可以跳出来，然后 [公式] 自然也有它自己的表达方式，之后的长度也都可以在S的整数倍的基础上调整得来。

对于本题来说，最大的 [公式] 的取值是 [公式] ，也就是说我们让任意两个距离大于90的石头距离为90就可以了，这样时间空间都满足了!

（S==T的情况直接特判）

 
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.Arrays;
 
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
 
    // 注意 hasNext 和 hasNextLine 的区别
    while (in.hasNext()) { // 注意 while 处理多个 case
        int n = in.nextInt();//表示独木桥的长度。
        int s = in.nextInt();//表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数
        int t = in.nextInt();//表示青蛙一次跳跃的最大距离
        int m = in.nextInt();//桥上石子的个数
        ArrayList<Integer> stones = new ArrayList();
        for(int i=0;i<m;i++) {//第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。
//所有相邻的整数之间用一个空格隔开。
            stones.add(in.nextInt());
        }
        Collections.sort(stones);//对M个石子进行排序，从小到大
 
        if(s==t) {
            singleJudge(s,stones);//输出青蛙过河最少需要踩到的石子数
        } else {
            rangeJudge(s,t,n,stones);//s！=t时候执行
        }
    }
}
 
public static void singleJudge(int s,ArrayList<Integer> stones) {
    int stoneNumber = 0;
    for(int i=0;i<stones.size();i++) {
        if(stones.get(i)%s == 0) {
            stoneNumber++;
        }
    }
    System.out.println(stoneNumber);//表示青蛙过河最少需要踩到的石子数
}
 
public static void rangeJudge(int s,int t,int n,ArrayList<Integer> stones) {
    int compressLen = compressBridgeLength(stones,n,t);
    int[] dp = new int[compressLen+t+1];//定义数组长度为compressLen+t+1
    Arrays.fill(dp,10000);//给数组填充10000数据
    dp[0] = 0;//数组第一元素初始化0
    int stoneNumber = 10000;//石头数量
    int maxStep = 0;//最大步数
    for(int i=s;i<=compressLen+t;i++) {
        maxStep = Math.max(maxStep,i);//求最大步数
        for(int j=s;j<=t;j++) {//递归找到最小的
            if(i>=j) {
                dp[i] = Math.min(dp[i],dp[i-j]);//求dp[i],dp[i-j]中小的
            }
        }
        if(stones.contains(i)) {//石头中包含i
            dp[i] +=1;//加1
        }
    }
 
    for(int i=compressLen;i<=maxStep;i++) {//递归范围从maxStep，找到最小的石头
        stoneNumber = Math.min(dp[i],stoneNumber);//求dp[i],stoneNumbe中小的
    }
    System.out.println(stoneNumber);
}
 
public static int compressBridgeLength(ArrayList<Integer> stones,int n,int t) {
    for(int i=1;i<stones.size();i++) {
        int distance = stones.get(i) - stones.get(i-1);//求石头i和i-1距离
        stones.set(i,stones.get(i-1) + distance%90);//求石头i赋值第i-1个石头距离加上 石头i和i-1距离除以90余数
    }
    n = (n - stones.get(stones.size()-1))%90 + stones.get(stones.size()-1);
    return n;
}
}