Minimum Time to Remove All Cars Containing Illegal Goods LeetCode solution in C++

1
class Solution {
2
 public:
3
  int minimumTime(string s) {
4
    int n = s.length();
5
    vector<int> dp(n, 0);
6
    if (s[n - 1] == '0') {
7
      dp[n - 1] = 0;
8
    } else {
9
      dp[n - 1] = 1;
10
    }
11
    for (int i = n - 2; i >= 0; i--) {
12
      if (s[i] == '0') dp[i] = dp[i + 1];
13
      if (s[i] == '1') {
14
        dp[i] = 2 + dp[i + 1];     // consider current index to be a middle one and remove
15
        dp[i] = min(dp[i], n - i); // or remove all to the right
16
      }
17
    }
18
    // now go from left to right
19
    int ans = dp[0];
20
    for (int i = 0; i < n - 1; i++) {
21
      ans = min(ans, i + 1 + dp[i + 1]); // cost of removing all from left and dp[i+1]
22
    }
23
    ans = min(ans, n); // taking overall minimum
24
    return ans;
25
  }
26
};