DEV Community

Miss Pooja Anilkumar Patel
Miss Pooja Anilkumar Patel

Posted on

1883. Leetcode Solution in Cpp

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;
  }
};

Enter fullscreen mode Exit fullscreen mode

Discussion (0)