forked from ttzztztz/leetcodeAlgorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path1541. Put Box.cpp
More file actions
28 lines (27 loc) · 910 Bytes
/
1541. Put Box.cpp
File metadata and controls
28 lines (27 loc) · 910 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
/**
* @param box: the boxes
* @param position: the positions
* @return: the maximum number of boxes you can put in
*/
int putBox(vector<int> &box, vector<int> &position) {
N = box.size(), M = position.size();
f = vector<vector<int>>(N + 1, vector<int>(M + 1, -1));
return dfs(box, position, 0, 0);
}
int dfs(const vector<int> &box, const vector<int> &position, int i, int j) {
if (i == N || j == M) return 0;
if (f[i][j] != -1) return f[i][j];
int answer = 0;
if (box[i] <= position[j]) {
answer = max(answer, 1 + dfs(box, position, i + 1, j + 1));
}
answer = max(answer, dfs(box, position, i, j + 1));
answer = max(answer, dfs(box, position, i + 1, j));
return f[i][j] = answer;
}
private:
vector<vector<int>> f;
int N, M;
};