I started practicing some DP problems. For some easy problems (like when there's only 1 arg whose value is changing in each recursive call) I'm able to change the memoized solution to tabulated solution. But I'm finding it hard for to do this when there are `>= 2 args` whose value is changing in each recursive call (and which are not very straightforward). For ex:. ↵
↵
Here's one question from leetcode contest (I hope pasting leetcode link here is not a problem):↵
↵
I was able to write a recursive (and thus memoized solution) but I couldn't figure out how to do it in tabulated form↵
↵
Here's the memoized solution:↵
↵
~~~~~↵
class Solution {↵
vector<vector<int>> space;↵
public:↵
int maximizeTheProfit(int n, vector<vector<int>>& offers) {↵
int on = (int)offers.size();↵
↵
sort(offers.begin(), offers.end(), [&](vector<int>& o1, vector<int>& o2) {↵
return o1.at(1) < o2.at(1);↵
});↵
↵
this->space.resize(on, vector<int>(on, -1));↵
return max_profit(offers, on, 0, -1);↵
}↵
↵
int max_profit(const vector<vector<int>>& offers, int n, int idx, int prev) {↵
if (idx == n) return 0;↵
↵
if (this->space[idx][prev + 1] != -1) return this->space[idx][prev + 1];↵
↵
int res = 0;↵
if (idx == 0 || prev == -1 || (offers[prev][1] < offers[idx][0])) {↵
res = max(res, offers[idx][2] + max_profit(offers, n, idx + 1, idx));↵
}↵
res = max(res, max_profit(offers, n, idx + 1, prev));↵
↵
return this->space[idx][prev + 1] = res; ↵
}↵
};↵
~~~~~↵
↵
For tabulation, I understand that outer loop should look like this:↵
↵
~~~~~↵
for (int i = on - 1; i >= 0; i--) {↵
}↵
~~~~~↵
↵
But I'm not able to understand how to write loop for the `prev` (inner loop). So far I understand that in tabulation, the prev should look between the `i` (i.e., from outer loop) and `on` (i.e., offers.size()). ↵
↵
Is there some blog/video and problems which can help me in getting good and converting memoized solution to tabulated ones ? I'm willing to practice more of these kinds of problem.↵
↵
(Please comment if anything is not clear in the post.)↵
↵
Thanks↵
↵
↵
↵
Here's one question from leetcode contest (I hope pasting leetcode link here is not a problem):
↵
I was able to write a recursive (and thus memoized solution) but I couldn't figure out how to do it in tabulated form↵
↵
Here's the memoized solution:↵
↵
~~~~~↵
class Solution {↵
vector<vector<int>> space;↵
public:↵
int maximizeTheProfit(int n, vector<vector<int>>& offers) {↵
int on = (int)offers.size();↵
↵
sort(offers.begin(), offers.end(), [&](vector<int>& o1, vector<int>& o2) {↵
return o1.at(1) < o2.at(1);↵
});↵
↵
this->space.resize(on, vector<int>(on, -1));↵
return max_profit(offers, on, 0, -1);↵
}↵
↵
int max_profit(const vector<vector<int>>& offers, int n, int idx, int prev) {↵
if (idx == n) return 0;↵
↵
if (this->space[idx][prev + 1] != -1) return this->space[idx][prev + 1];↵
↵
int res = 0;↵
if (idx == 0 || prev == -1 || (offers[prev][1] < offers[idx][0])) {↵
res = max(res, offers[idx][2] + max_profit(offers, n, idx + 1, idx));↵
}↵
res = max(res, max_profit(offers, n, idx + 1, prev));↵
↵
return this->space[idx][prev + 1] = res; ↵
}↵
};↵
~~~~~↵
↵
For tabulation, I understand that outer loop should look like this:↵
↵
~~~~~↵
for (int i = on - 1; i >= 0; i--) {↵
}↵
~~~~~↵
↵
But I'm not able to understand how to write loop for the `prev` (inner loop). So far I understand that in tabulation, the prev should look between the `i` (i.e., from outer loop) and `on` (i.e., offers.size()). ↵
↵
Is there some blog/video and problems which can help me in getting good and converting memoized solution to tabulated ones ? I'm willing to practice more of these kinds of problem.↵
↵
(Please comment if anything is not clear in the post.)↵
↵
Thanks↵
↵
↵
