Problem statement

https://leetcode.com/problems/minimum-skips-to-arrive-at-meeting-on-time/

Solution

Let us use dynamic programming here with the following states, we have dp(i, k), where:

  1. i is the number of roads we traversed so far.
  2. j is number of skips we did.
  3. output of this function is minimum arriving time.

Note, that because times can be not-integer, we want to multiply everything by speed S, so we will work only with integers from now on. Let us discuss function dp(i, k) now:

  1. If k < 0, it means, we out of skips, we made more skips than it was possible and we need to return infinity.
  2. If i < 0, it means that we did not traverse any road, so we spend 0 time for this.
  3. Finally, there can be two options: we can make skip the break and then we have dist[i] + dp(i-1, k-1) time or we do not skip it. If we do not skip break, we need to round up our time to the nearest bigger number divisible by S.

Complexity

We have O(n^2) states with at most 2 transitions from one to others, so time and space complexity is O(n^2).

Code

class Solution:
    def minSkips(self, dist, S, H):
        @lru_cache(None)
        def dp(i, k):
            if k < 0: return float("inf")
            if i < 0: return 0
            return dist[i] + min(dp(i-1, k-1), (dp(i-1, k) + S - 1)//S*S)
        
        if sum(dist) > S*H: return -1
        n = len(dist)
        return next(k for k in range(n+1) if dp(n - 1, k) <= H*S)

2 liner

class Solution:
    def minSkips(self, D, S, H):
        f = lru_cache(None)(lambda i,k: H*S if k < 0 else 0 if i < 0 else (D[i] + min(f(i-1, k-1), (f(i-1, k) + S - 1)//S*S)))
        return next(k for k in range(len(D)) if f(len(D) - 1, k) <= H*S) if sum(D) <= S*H else -1