class Solution {
public:
int maxValue(vector<vector<int>> &events, int k) {
sort(events.begin(), events.end(), [](auto &a, auto &b) { return a[1] < b[1]; }); // 按照结束时间排序
int n = events.size(), f[n + 1][k + 1];
memset(f, 0, sizeof(f));
for (int i = 0; i < n; ++i) {
int p = lower_bound(events.begin(), events.begin() + i, events[i][0],
[](auto &e, int lower) { return e[1] < lower; }) - events.begin();
for (int j = 1; j <= k; ++j)
// 为什么是 p 不是 p+1:上面算的是 >= events[i][0],-1 后得到 < events[i][0],但由于还要 +1,抵消了
f[i + 1][j] = max(f[i][j], f[p][j - 1] + events[i][2]);
}
return f[n][k];
}
};
作者:灵茶山艾府
#include
#include
#include
#include
#include
using namespace std;
class Solution {
public:
int maxValue(vector<vector<int> >& events, int k) {
sort(events.begin(), events.end(),[](const vector<int>& a, const vector<int>& b){ return a[1] < b[1];});
for (const auto& row : events) {
for (const auto& element : row) {
std::cout << element << " ";
}
std::cout << std::endl;
}
int n = events.size();
int f[n+1][k+1];
memset(f,0,sizeof(f));
for(int i=0; i<n; i++){
int p = lower_bound(events.begin(), events.begin()+i, events[i][0], [](const vector<int>& e, const int lower){ return e[1] < lower;}) - events.begin();
std::cout <<"0 -- "<<i<<","<<"p:" << p << std::endl;
for(int j=1; j<=k; j++){
f[i+1][j] = max(f[i][j], f[p][j-1]+events[i][2]);
}
for(int i=0; i<=n; i++){
for(int j=0; j<=k; j++){
std::cout << f[i][j] << " ";
}
std::cout << std::endl;
}
}
return f[n][k];
}
};
int main(){
vector<vector<int> > events = {{1,1,10},{1,1,5},{2,2,1},{3,3,1}};
int k = 3;
Solution s;
int ans = s.maxValue(events, k);
std::cout << "ans:" << ans << std::endl;
return 0;
}
gdb 断点
events = {{1,1,10},{1,1,5},{2,2,1},{3,3,1}}
f[2][k] = max(f[1][k], f[0][k-1]+events[1][2])
因为{1,1,10} 和 {1,1,5}, 是相同的路径,f[1] 和 f[2] 是相同的,这个动态规划可以解决路径一样的冲突。
{1,1,10},{1,1,5},{2,2,1}
events[2] 基于 events[1] 和 events[0], 所以f[3] 是基于 f[2]的。