House Robber II LeetCode solution in C++

1
class Solution {
2
 public:
3
  int rob(vector<int> &nums) {
4
    int n = nums.size();
5
    if (n == 1) {
6
      return nums[0];
7
    }
8
    // dp[n][2][1]
9
    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(2, vector<int>(2, -1)));
10

11
    int maxm = 0;
12
    for (int i = 0; i < n; i++) {
13
      for (int j = 0; j < 2; j++) {
14
        for (int k = 0; k < 2; k++) {
15
          maxm = max(maxm, dp_fun(dp, i, j, k, nums));
16
        }
17
      }
18
    }
19

20
    return maxm;
21
  }
22

23
  int dp_fun(vector<vector<vector<int>>> &dp, int ind, int num, int last, vector<int> &ar) {
24
    int n = ar.size();
25
    if (dp[ind][num][last] == -1) {
26
      if (ind == 0) {
27
        if (last == 1) {
28
          dp[ind][num][last] = 0;
29
        } else {
30
          if (num == 1) {
31
            dp[ind][num][last] = ar[ind];
32
          } else {
33
            dp[ind][num][last] = 0;
34
          }
35
        }
36
      } else if (ind == n - 1) {
37
        if (num == 0) {
38
          dp[ind][num][last] = 0;
39
        } else {
40
          if (last == 0) {
41
            dp[ind][num][last] = dp_fun(dp, ind - 1, 1, 0, ar);
42
          } else {
43
            dp[ind][num][last] = ar[ind] + dp_fun(dp, ind - 1, 0, 1, ar);
44
          }
45
        }
46
      } else {
47
        if (num == 1) {
48
          dp[ind][num][last] =
49
              max(ar[ind] + dp_fun(dp, ind - 1, 0, last, ar), dp_fun(dp, ind - 1, 1, last, ar));
50
        } else {
51
          dp[ind][num][last] = dp_fun(dp, ind - 1, 1, last, ar);
52
        }
53
      }
54
    }
55
    return dp[ind][num][last];
56
  }
57
};