本文主要是介绍LeetCode 1601. 最多可达成的换楼请求数目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：
力扣
https://leetcode-cn.com/problems/maximum-number-of-achievable-transfer-requests/
【分析】直接回溯法遍历所有的request，并用一个cnt数组记录每栋楼里的人数，初始时都是0，如果某个request被选中，那么下标为from的cnt--，下标为to的cnt++。当回溯层数到达request长度时判断cnt是否还是为0。
class Solution {int ans = 0;int k;int[][] req;public void dfs(int t, int j, int[] cnt){if(t == k){int i;for(i = 0; i < cnt.length; i++){if(cnt[i] != 0) break;}if(i == cnt.length) {System.out.println(j);ans = Math.max(ans, j);}}else{int[] tmp = cnt.clone();dfs(t + 1, j, tmp);tmp[req[t][1]] ++;tmp[req[t][0]] --;dfs(t + 1, j + 1, tmp);}}public int maximumRequests(int n, int[][] requests) {int[] cnt = new int[n];req = requests;k = requests.length;dfs(0, 0, cnt);return ans;}
}需要特别注意！这里的cnt数组要clone一份，不然只传cnt的话下一层修改会影响上一层的cnt。
【改进】加入剪枝，如果剩下的request数目加上先前已经被选择的request数目小于目前的最大值的话直接return出去就行；另外这里的cnt可以不复制一份新的，只要记得在调完dfs后把值复原就行了。
class Solution {int ans = 0;int k;int[][] req;public void dfs(int t, int j, int[] cnt){if(t == k){int i;for(i = 0; i < cnt.length; i++){if(cnt[i] != 0) break;}if(i == cnt.length) {System.out.println(j);ans = Math.max(ans, j);}}else{if(j + k - t < ans) return;dfs(t + 1, j, cnt);cnt[req[t][1]] ++;cnt[req[t][0]] --;dfs(t + 1, j + 1, cnt);cnt[req[t][1]] --;cnt[req[t][0]] ++;}}public int maximumRequests(int n, int[][] requests) {int[] cnt = new int[n];req = requests;k = requests.length;dfs(0, 0, cnt);return ans;}
}这篇关于LeetCode 1601. 最多可达成的换楼请求数目的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
