You are given an integer hoursBefore, the number of hours you have to travel to your meeting. To arrive at your meeting, you have to travel through n roads. The road lengths are given as an integer array dist of length n, where dist[i] describes the length of the ith road in kilometers. In addition, you are given an integer speed, which is the speed (in km/h) you will travel at.

After you travel road i, you must rest and wait for the next integer hour before you can begin traveling on the next road. Note that you do not have to rest after traveling the last road because you are already at the meeting.


	For example, if traveling a road takes 1.4 hours, you must wait until the 2 hour mark before traveling the next road. If traveling a road takes exactly&nbsp;2&nbsp;hours, you do not need to wait.


However, you are allowed to skip some rests to be able to arrive on time, meaning you do not need to wait for the next integer hour. Note that this means you may finish traveling future roads at different hour marks.


	For example, suppose traveling the first road takes 1.4 hours and traveling the second road takes 0.6 hours. Skipping the rest after the first road will mean you finish traveling the second road right at the 2 hour mark, letting you start traveling the third road immediately.


Return the minimum number of skips required to arrive at the meeting on time, or -1 if it is impossible.

&nbsp;
Example 1:

Input: dist = [1,3,2], speed = 4, hoursBefore = 2
Output: 1
Explanation:
Without skipping any rests, you will arrive in (1/4 + 3/4) + (3/4 + 1/4) + (2/4) = 2.5 hours.
You can skip the first rest to arrive in ((1/4 + 0) + (3/4 + 0)) + (2/4) = 1.5 hours.
Note that the second rest is shortened because you finish traveling the second road at an integer hour due to skipping the first rest.


Example 2:

Input: dist = [7,3,5,5], speed = 2, hoursBefore = 10
Output: 2
Explanation:
Without skipping any rests, you will arrive in (7/2 + 1/2) + (3/2 + 1/2) + (5/2 + 1/2) + (5/2) = 11.5 hours.
You can skip the first and third rest to arrive in ((7/2 + 0) + (3/2 + 0)) + ((5/2 + 0) + (5/2)) = 10 hours.


Example 3:

Input: dist = [7,3,5,5], speed = 1, hoursBefore = 10
Output: -1
Explanation: It is impossible to arrive at the meeting on time even if you skip all the rests.


&nbsp;
Constraints:


	n == dist.length
	1 &lt;= n &lt;= 1000
	1 &lt;= dist[i] &lt;= 105
	1 &lt;= speed &lt;= 106
	1 &lt;= hoursBefore &lt;= 107


from math import *
class Solution:
    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:
        n=len(dist)
		# Error Range 10^-9 can be ignored in ceil, so we will subtract this value before taking ceil 
        e=1e-9
        mat=[[0 for i in range(n)]for j in range(n)]
        mat[0][0]=dist[0]/speed
		# Initialization 
		# Values where 0 skips are considered
        for i in range(1,n):
            mat[i][0]=ceil(mat[i-1][0]-e)+dist[i]/speed
        for i in range(1,n):
            for j in range(1,i):
                mat[i][j]=min(ceil(mat[i-1][j]-e),mat[i-1][j-1])+dist[i]/speed
            mat[i][i]=mat[i-1][i-1]+dist[i]/speed
        for i in range(n):
            if mat[-1][i]<=hoursBefore:
                return i
        return -1
class Solution {
    public int minSkips(int[] dist, int speed, int hoursBefore) {
        int N = dist.length, INF = (int)1e9;
        int[] dp = new int[N];
        Arrays.fill(dp, INF);
        dp[0]=0; // before we start, we have a time of 0 for 0 cost
        for (int i = 0 ; i<N; i++){
            for (int j = i; j >= 0; j--){ // j (cost) is at most i (num of element-1) so we start from there.
                dp[j]=Math.min(j==0?INF:dp[j-1]+dist[i], ceil(dp[j], speed)+dist[i]);
            }
        }
        for (int i = 0; i < N; i++){ // find the min cost (i) such that the min time is no greater than hoursBefore
            if (ceil(dp[i],speed)/speed<=hoursBefore){
                return i;
            }
        }
        return -1;
    }

    private int ceil(int n, int s){
        return n+(s-n%s)%s;
    }
}
class Solution {
public:
    vector<int>D;
    long long s, last;
    long long memo[1010][1010];
    long long dfs_with_minimum_time_with_k_skip(int idx, int k) {
        if (idx < 0 ) return 0;
        long long &ret = memo[idx][k];
        if (ret != -1 ) return ret;
        long long d = dfs_with_minimum_time_with_k_skip(idx - 1, k) + D[idx];
        if (d % s) d = ((d/s) + 1)*s;
        ret = d;
        if (k > 0 ) ret = min(ret, dfs_with_minimum_time_with_k_skip(idx - 1, k - 1) + D[idx]);
        return ret;
    }
    int minSkips(vector<int>& dist, int speed, int hoursBefore) {
        int n = dist.size();
        D = dist, s = speed;
        int lo = 0, hi = n;
        long long d = 0, H = hoursBefore;
        H *=s;
        last = dist[n-1];
        for (int dd : dist) d += dd;
        memset(memo, -1, sizeof(memo));
        if (d /s > hoursBefore) return -1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            long long h = dfs_with_minimum_time_with_k_skip(n-2, mid) + last; // we should start from second last since it is not required to rest on last road
            if (h <= H ) hi = mid;
            else lo = mid + 1;
        }
        return lo == D.size() ? -1 : lo;

    }
};
var minSkips = function(dist, speed, hoursBefore) {

    // calculates the time needed to rest
    const getRestTime = (timeFinished) => {
        if (timeFinished === Infinity) return 0;
        return (speed - (timeFinished % speed)) % speed;
    }

    // dp is a n x n matrix with
    // dp[destinationIndex][numRestsSkipped] = timeTaken
    //
    // destinationIndex: the index of the destination being observed
    // numRestsSkipped: number of rests taken
    // timeTaken: minimum time taken to travel to destination taking numRests number of rests
    const dp = [...dist].map(() => new Array(dist.length).fill(Infinity));

    // start with the first stop
    dp[0][0] = dist[0] + getRestTime(dist[0]) // took a rest at the first destination
    dp[0][1] = dist[0]; // did not take a rest at the first destination

    for (let distIdx = 1; distIdx < dist.length; distIdx++) {
        const distance = dist[distIdx];
        let timeToDestWithoutrest = dp[distIdx - 1][0] + distance;
        dp[distIdx][0] = timeToDestWithoutrest + getRestTime(timeToDestWithoutrest);
        for (let numRestsSkipped = 1; numRestsSkipped <= distIdx + 1; numRestsSkipped++) {
            // calculate the time if taking a rest here
            timeToDestWithoutrest = dp[distIdx - 1][numRestsSkipped] + distance;
            const didRestTimeToDest = timeToDestWithoutrest + getRestTime(timeToDestWithoutrest);

            // calculate the time without resting here
            const didntRestTimeToDest = dp[distIdx - 1][numRestsSkipped - 1] + distance

            // store the best time in the dp
            dp[distIdx][numRestsSkipped] = Math.min(dp[distIdx][numRestsSkipped],
                                                    didRestTimeToDest,
                                                    didntRestTimeToDest);
        }
    }

    // find the minimum number of rests visiting all the destinations
    const speedHours = speed * hoursBefore;
    for (let numRests = 0; numRests < dist.length; numRests++) {
        if (dp[dist.length - 1][numRests] <= speedHours) {
            return numRests;
        }
    }
    return -1;
};
Minimum Skips to Arrive at Meeting On Time