• Time:O(n^2)
• Space:O(n^2)

## C++

``````class Solution {
public:
int minSkips(vector<int>& dist, int speed, int hoursBefore) {
constexpr double kInf = 1e7;
constexpr double kEps = 1e-9;
const int n = dist.size();
// dp[i][j] := min time w/ prev i-th road and j skips
vector<vector<double>> dp(n + 1, vector<double>(n + 1, kInf));
dp[0][0] = 0;

for (int i = 1; i <= n; ++i) {
const double d = dist[i - 1];
dp[i][0] = ceil(dp[i - 1][0] + 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;
}
};
``````

## JAVA

``````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] := min time w/ prev i-th road and j skips
double[][] dp = new double[n + 1][n + 1];
Arrays.stream(dp).forEach(row -> Arrays.fill(row, kInf));
dp[0][0] = 0;

for (int i = 1; i <= n; ++i) {
final double d = dist[i - 1];
dp[i][0] = Math.ceil(dp[i - 1][0] + 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;
}
}
``````

## Python

``````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] := min time w/ prev i-th road and j skips
dp = [[kInf] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 0

for i, d in enumerate(dist, 1):
dp[i][0] = ceil(dp[i - 1][0] + d / speed - kEps)
for j in range(1, i + 1):
dp[i][j] = min(dp[i - 1][j - 1] + d / speed,
ceil(dp[i - 1][j] + d / speed - kEps))

for j, time in enumerate(dp[-1]):
if time <= hoursBefore:
return j

return -1
``````