Minimum Sideway Jumps LeetCode solution in C++

1
class Solution {
2
 public:
3
  int func(int i, int l, vector<int> &obstacles, vector<vector<int>> &dp) {
4
    if (i == obstacles.size() - 2) {
5
      if (obstacles[i + 1] == l) return 1;
6
      return 0;
7
    }
8

9
    if (dp[i][l] != -1) return dp[i][l];
10

11
    if (obstacles[i + 1] != l) {
12
      return dp[i][l] = func(i + 1, l, obstacles, dp);
13
    }
14

15
    int b = INT_MAX;
16
    for (int j = 1; j <= 3; j++) {
17
      if (l == j) continue;
18
      if (obstacles[i] == j) continue;
19
      b = min(b, 1 + func(i, j, obstacles, dp));
20
    }
21

22
    return dp[i][l] = b;
23
  }
24

25
  int minSideJumps(vector<int> &obstacles) {
26
    int n = obstacles.size();
27
    vector<vector<int>> dp(n, vector<int>(4, -1));
28
    return func(0, 2, obstacles, dp);
29
  }
30
};