链接：https://www.nowcoder.com/questionTerminal/9fededa1b63a41798e5d43344d7bf216?answerType=1&f=discussion
来源：牛客网

有10^8个村庄排在一条公路上，依次编号为0~~10^8-1，相邻村庄距离为1，其中有n个村庄居住着牛牛，居住着牛牛的村庄从小到大依次为a0~~an-1，其中保证a0=0.
现在需要建设车站，有两个要求必须被满足：
1、每个有牛牛居住的村庄必须修建车站。
2、相邻车站的距离必须为1或为某个质数。
现给出n和a数组，求需要建设车站的最小数量。
示例1
输入
3,[0,7,11]
输出
4
说明
在0,7,8,11处建造车站，差值分别为7,1,3，符合要求

备注:
输入数据包含一个数n和一个长度为n的数组a，数组a的下标为0~n-1，保证a数组递增，且a0=0。
输出一个整数，表示答案。
1<=n<=1000，a数组中数值保证小于10^8

思路

1. 所有有人住的地方必须建站。
2.难点就在于处理差值到底需要多少个素数和1累加得到。如果最暴力的想法可能是直接搜索所有组合并取最小。显然时间是无法接受的。所以这里考虑动态规划来做。不难想到, 当距离差值为n，那么其必定由a + b + ... + c得到，其中a,b,.....c必定为1或者素数。所以转移为

dp[n] = min(dp[n], dp[n - k] + 1) 其中k为素数或为1;

3.我们预处理出距离最大的素数集(这里用的欧拉筛(还是TLE了。然后对dp数组进行处理，得到距离为1~max所需的最小建站。
4.对初始值sum进行累加即得到答案
5.并没有通过只是分享思路结论是真的不知道，当数据量相对较小时如 10^6 跑这个算法应该没什么问题.

import java.util.*;


public class Solution {
    public int work (int n, int[] a) {
        // 定义max为相隔两站的最大距离
        int max = Integer.MIN_VALUE;
        for(int i = 1; i < a.length; i++){
            max = Math.max(max, a[i] - a[i - 1]);
        }
        // 欧拉筛 筛出0 ~ 两站最大距离的所有值是否为素数.
        boolean[] check = primeFun(max + 1);
        // 定义sum为总共车站数 其中 居住必须建站初始化为住户数  之后+上距离不为1且不为素数所需要新修的站点数量
        int sum = a.length;
        // dp 预处理两站距离n 最少所需的站点数
        // 因为距离 肯定是由1和素数进行相加得到 所以转移为 dp[n] = min(dp[n], dp[n - k] + 1) 其中k为素数或为1;
        int[] dp = new int[max + 1]; // dp[i]表示 相差距离为i 最小需要修建的车站个数
        for(int i = 1; i <= max; i++){
            // 距离为素数 不需要重新建站
            if(!check[i]){
                dp[i] = 0;
            } else {
                // 距离不为素数 初始化为无穷大并进行转移
                dp[i] = Integer.MAX_VALUE;
                for(int j = 1; j < i; j++){
                    if(!check[j]){
                        dp[i] = Math.min(dp[i], dp[i - j] + 1);
                    }
                }
            }
        }
        for(int i = 1; i < a.length; i++){
            int val = a[i] - a[i - 1];
            // val 两站差值  直接住户数 + 差值最小需要建站数即可
            sum += dp[val];
        }
        return sum;
        // TLE 只是分享下思路.  这结论真不知道
    }

    // 欧拉筛
    private static boolean[] primeFun(int n){
        // check[i] = true 代表是非素数 check[i] = false 代表为素数
        boolean[] check = new boolean[n + 1];
        // 讲道理 这里 check[1]也要为true 但是题意给定 1 也为满足条件 所以设置为false;
        check[0] = true;
        ArrayList<Integer> prime = new ArrayList<>();
        for(int i = 2; i <= n; i++){
            if(!check[i]){
                prime.add(i);
            }
            for(int j = 0; j < prime.size() && i * prime.get(j) <= n; j++){
                check[i * prime.get(j)] = true;
                if(prime.get(j) % i == 0){
                    break;
                }
            }
        }
        return check;
    }
}

车站建造问题

思路

dp[n] = min(dp[n], dp[n - k] + 1) 其中k为素数或为1;