leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1824.cpp (751B)

      1 class Solution {
      2   public:
      3     int minSideJumps(const vector<int> &obstacles) const {
      4         static unsigned dp[500002][3];
      5         const int n = size(obstacles);
      6 
      7         memset(dp, 0xF0, sizeof(dp));
      8         memset(dp[n - 1], 0x00, sizeof(dp[n]));
      9         for (int i = n - 2; i >= 0; i--) {
     10             for (int j = 0; j < 3; j++) {
     11                 if (obstacles[i + 1] == j + 1) continue;
     12                 if (obstacles[i] == j + 1) continue;
     13                 dp[i][j] = dp[i + 1][j];
     14             }
     15 
     16             dp[i][0] = min({dp[i][0], dp[i][1] + 1, dp[i][2] + 1});
     17             dp[i][1] = min({dp[i][1], dp[i][0] + 1, dp[i][2] + 1});
     18             dp[i][2] = min({dp[i][2], dp[i][0] + 1, dp[i][1] + 1});
     19         }
     20 
     21         return dp[0][1];
     22     }
     23 };