leetcode 1626. 无矛盾的最佳球队-Best Team With No Conflicts

Problem: 1626. 无矛盾的最佳球队- Best Team With No Conflicts

深度优先搜索，记忆化，拿到最大值就可以了

Code

class Solution { public: int mem[1001][1001], n; int dfs(vector<pair<int, int>>& arr, int index, int preindex) { if(index == n) return 0; int preAge = -1, preSco = -1; if(preindex >= 0) { if(mem[index][preindex] > 0) return mem[index][preindex]; preAge = arr[preindex].first; preSco = arr[preindex].second; } int nowage = arr[index].first; int nowsco = arr[index].second; int r1 = INT_MIN/100, r2 = INT_MIN/100, mx; if((nowage == preAge) || (preSco <= nowsco)) { r1 = dfs(arr, index + 1, index) + arr[index].second; } r2 = dfs(arr, index + 1, preindex); mx = max(r1, r2); if(preindex >= 0) mem[index][preindex] = mx; return mx; } int bestTeamScore(vector<int>& scores, vector<int>& ages) { n = scores.size(); memset(mem, -1, sizeof(mem)); vector<pair<int, int>> arr; for(int i = 0; i < n; i++) { arr.push_back({ages[i], scores[i]}); } sort(arr.begin(), arr.end()); int mx = 0, pre, now, sum, sco, a; int r = dfs(arr, 0, -1); return r; } };