2023-08-19 20:57 门头沟学院 前端工程师
关注
美团笔试
给定a数组，求b数组的数量，规则为：
1. 对于任意的i， ai != bi
2. a数组的和等于b数组的和
各位大佬的思路是啥？
1. 对于任意的i， ai != bi
2. a数组的和等于b数组的和
各位大佬的思路是啥？
全部评论
感谢信收集桶
西安电子科技大学 C++
dfs3.33
三过大厂而不入
哈尔滨工业大学（深圳） Java
用的dp，测试用例都过了，一交0%😡
electronic
门头沟学院 前端工程师
递归做半天，0%
冬冬瓜皮
蚌埠坦克学院 测试开发
背包问题
xxx_yy
浙江科技学院 C++
乱写了一个记搜就过了
想到了是01背包问题，但还是用dfs做了，js简单优化了下3.33
在摸鱼的牛肉丸很讲原则
门头沟学院 C++
回溯3.33，超时
一个善良且老实的人
门头沟学院 Java
dp[i][j]：表示构建新数组来到i位置 此时数组的和还剩余j
==>dp[数组长度][0] = 1:
==>第一列，最后一行答案已知
==>需要知道：dp[0][sum]的值
==>dp[i][j] = dp[i + 1][j - k]的和 其中j-k>=0
但是我只能过6%，不知道哪的问题
我的代码，看看佬能看出来我哪有问题
// Scanner sc = new Scanner(System.in);
// int n = sc.nextInt();
// int[] resource = new int[n];
// for (int i = 0; i < n; i++) {
// resource[i] = sc.nextInt();
// }
// int sum = Arrays.stream(resource).sum();
// long[][] dp = new long[n + 1][sum + 1];
// dp[n][0] = 1;
// for(int i = n - 1;i >= 0;i--){
// for(int j = 1;j < dp[0].length;j++){
// long res = 0;
// for(int k = 1;j - k >= 0;k++){
// if(resource[i] == k)
// continue;
// res = res + dp[i + 1][j - k] % 1000000007;
// }
// res += dp[i + 1][j - 1];
// dp[i][j] = res;
// }
// }
// System.out.println(dp[0][sum]);
virtualx
中国科学技术大学 C++
维护长度为sum的数组做dp，dp[i]表示当前用i来满足自当前元素之后的所有元素的满足要求的数量，然后想办法从后到前遍历所有元素维护这个数组，最后输出dp[sum]
wuuuummm
门头沟学院 C++
蹲
小达qwq
中国科学技术大学 C++
dp背包，3ms 400KB
小牛414
西安交通大学 C++
我用的递归 测试用例都过了 提交为0
待失业选手
东南大学 Java
直接记忆化搜索就可以过
招聘爱好
吉林大学 引擎开发
这个线性dp,和京东的第二题一样
惜_叩
雅安职业技术学院 C++
超时了，原本想把递归换成栈的，时间不够了
相关推荐
查看30道真题和解析