Problem: 1751. 最多可以参加的会议数目 II三种方案的两种超时了方案1、回溯超时了排序以后两种选择的要么选要么不选的方案2、从后向前动态规划超时了找到比当前开始小的会议然后计算最大值改进方案的用二分搜索方案3、从前向后动态规划通过了找到比当前结束大的会议然后计算最大值二分搜索即可方案3通过的 Codeclass Solution { public: int maxValue(vectorvectorint events, int k) { int n events.size(), mx events[0][2]; bool same true; vectorvectorint dp(n, vectorint(k 1, 0)); sort(events.begin(), events.end()); vectorint tr; for(int i 0; i n; i) { dp[i][1] events[i][2]; tr.push_back(events[i][0]); mx max(mx, dp[i][1]); if(events[i][0] ! events[i][1]) same false; } if(k1) return mx; if(same) { int sum 0; for(int i n-1; i max(0, n-k); i--) sum events[i][2]; return sum; } int ind, num; for(int i 0; i n; i) { ind upper_bound(tr.begin() i 1, tr.end(), events[i][1]) - tr.begin(); for(int j ind; j n; j) { num events[j][2]; for(int w 2; w k; w) { dp[j][w] max(dp[j][w], dp[i][w-1] num); } } } for(int i 0; i n; i) { for(int j 1; j k; j) { mx max(mx, dp[i][j]); } } return mx; } };方案1 回溯Codeclass Solution { public: int n; vectorvectorint dp; int dfs(vectorvectorint events, int index, int preChoose, int k) { if(index n || k 0) return 0; // if(dp[index][k] 0 events[preChoose][1] events[index][0]) { // return dp[index][k]; // } int r1 -999999999, r2 -999999999; if(preChoose 0 || events[preChoose][1] events[index][0]) { r1 dfs(events, index 1, index, k - 1) events[index][2]; } r2 dfs(events, index 1, preChoose, k); r1 max(r1, r2); dp[index][k] r1; return r1; } int maxValue(vectorvectorint events, int k) { n events.size(); int mx events[0][2]; bool same true; sort(events.begin(), events.end()); for(int i 0; i n; i) { mx max(mx, events[i][2]); if(events[i][0] ! events[i][1]) same false; } if(k1) return mx; if(same) { int sum 0; for(int i n-1; i max(0, n-k); i--) sum events[i][2]; return sum; } dp.assign(n, vectorint(k 1, -1)); int ret dfs(events, 0, -1, k); return ret; } };方案2 动态规划2class Solution { public: int maxValue(vectorvectorint events, int k) { int n events.size(), mx events[0][2]; bool same true; vectorvectorint dp(n, vectorint(k 1, 0)); sort(events.begin(), events.end()); for(int i 1; i k; i) dp[0][i] events[0][2]; for(int i 0; i n; i) { dp[i][1] events[i][2]; mx max(mx, dp[i][1]); if(events[i][0] ! events[i][1]) same false; } if(k1) return mx; if(same) { int sum 0; for(int i n-1; i max(0, n-k); i--) sum events[i][2]; return sum; } int pre, sco; for(int i 1; i n; i) { pre events[i][0]; sco events[i][2]; for(int w i - 1; w 0; w--) { if(events[w][1] pre) { for(int j 2; j k; j) { dp[i][j] max(dp[i][j], dp[w][j-1] sco); mx max(mx, dp[i][j]); } } } } return mx; } };