# 1883. Minimum Skips to Arrive at Meeting On Time    • Time: $O(n^2)$
• Space: $O(n^2)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public: int minSkips(vector& dist, int speed, int hoursBefore) { constexpr double kInf = 1e7; constexpr double kEps = 1e-9; const int n = dist.size(); // dp[i][j] := the minimum time, where i is the number of roads we traversed // so far and j is the number of skips we did vector> dp(n + 1, vector(n + 1, kInf)); dp = 0; for (int i = 1; i <= n; ++i) { const double d = dist[i - 1]; dp[i] = ceil(dp[i - 1] + d / speed - kEps); for (int j = 1; j <= i; ++j) dp[i][j] = min(dp[i - 1][j - 1] + d / speed, ceil(dp[i - 1][j] + d / speed - kEps)); } for (int j = 0; j <= n; ++j) if (dp[n][j] <= hoursBefore) return j; return -1; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public int minSkips(int[] dist, int speed, int hoursBefore) { final double kInf = 1e7; final double kEps = 1e-9; final int n = dist.length; // dp[i][j] := the minimum time, where i is the number of roads we traversed // so far and j is the number of skips we did double[][] dp = new double[n + 1][n + 1]; Arrays.stream(dp).forEach(A -> Arrays.fill(A, kInf)); dp = 0; for (int i = 1; i <= n; ++i) { final double d = dist[i - 1]; dp[i] = Math.ceil(dp[i - 1] + d / speed - kEps); for (int j = 1; j <= i; ++j) dp[i][j] = Math.min(dp[i - 1][j - 1] + d / speed, Math.ceil(dp[i - 1][j] + d / speed - kEps)); } for (int j = 0; j <= n; ++j) if (dp[n][j] <= hoursBefore) return j; return -1; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution: def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int: kInf = 10**7 kEps = 1e-9 n = len(dist) # dp[i][j] := the minimum time, where i is the number of roads we traversed # so far and j is the number of skips we did dp = [[kInf] * (n + 1) for _ in range(n + 1)] dp = 0 for i, d in enumerate(dist, 1): dp[i] = math.ceil(dp[i - 1] + d / speed - kEps) for j in range(1, i + 1): dp[i][j] = min(dp[i - 1][j - 1] + d / speed, math.ceil(dp[i - 1][j] + d / speed - kEps)) for j, time in enumerate(dp[-1]): if time <= hoursBefore: return j return -1