shopee笔试求和那道题,用DP只对了75%,找不出疏漏

就是n个数找和为sum的组合个数那道题
int main()
{
    int n, sum;
    cin >> n >> sum;

    for (int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;
        num.push_back(tmp);
    }

    vector<vector><int>> dp(num.size(), vector<int>(sum + 1, 0));
    // dp[i][j] 为以num[0..i]中数字组合出的和为j的组合数
    dp[0][num[0]] = 1;

    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j <= sum; j++)
        {
            if (j - num[i] > 0)
                dp[i][j] = dp[i - 1][j - num[i]] + dp[i - 1][j];
            else if (j == num[i])
                dp[i][j] = dp[i - 1][j] + 1;
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    cout << dp[n - 1][sum] << endl;
    return 0;
}
求大佬解答
#Shopee##笔试题目#
全部评论
请问笔试是几点到几点呀?
点赞 回复 分享
发布于 2019-08-09 08:45
dp[0][0] = true; 不然你这个dp就变成第一个数字必选
点赞 回复 分享
发布于 2019-07-28 17:50
java过了100 参考一下吧public static int findways(int[] array,int sum){ int length = array.length; int[][] dp =new int[length+1][sum+1]; for (int i = 0; i < sum+1; i++) { dp[0][i] = 0; } dp[0][0] = 1; for (int i = 1; i <=length ; i++) { for (int j = 0; j <=sum ; j++) { dp[i][j] = dp[i-1][j]; if(j>=array[i-1]) dp[i][j]+=dp[i-1][j-array[i-1]]; } } return dp[length][sum]; }
点赞 回复 分享
发布于 2019-07-28 12:28
第二批笔试同问,都考一些什么题啊
点赞 回复 分享
发布于 2019-07-28 10:58
大佬们  有几道笔试题   都是什么题啊
点赞 回复 分享
发布于 2019-07-28 10:56
dp数组int 改为 long
点赞 回复 分享
发布于 2019-07-28 09:04
可以压缩一下状态?毕竟每一次的状态更新只和上一次有关。
点赞 回复 分享
发布于 2019-07-28 00:26
菜鸟问下:你们最后一题是怎么处理输入的啊,我用的C++,下面的代码不行啊,因为必须遇到非法的输入字符才行啊。     笔试结束后,我在本地IDE上先用getline(cin,str)接收,然后分解出各个整数是可行的。但是很麻烦(只能说以后没办法在用)   vector<int> a;     int temp;     while (cin >> temp)     {         a.push_back(temp);     }
点赞 回复 分享
发布于 2019-07-27 23:08
题目是啥 楼主能说说吗
点赞 回复 分享
发布于 2019-07-27 21:22
大于等于吧。
点赞 回复 分享
发布于 2019-07-27 21:16
。。。
点赞 回复 分享
发布于 2019-07-27 21:15
全是正整数可以把大于sum的都剪掉
点赞 回复 分享
发布于 2019-07-27 21:09
同75%
点赞 回复 分享
发布于 2019-07-27 21:07
同25%
点赞 回复 分享
发布于 2019-07-27 21:06
用broce_force,只能A 25%
点赞 回复 分享
发布于 2019-07-27 21:05
这输入输出真的把我心态搞崩了
点赞 回复 分享
发布于 2019-07-27 21:04
25%
点赞 回复 分享
发布于 2019-07-27 21:04
数组里可能会出现零,所以比如n为7 sum=15 5 5 15 2 3 0 0 每一次dfs 的值等于sum时,count不是+1,是+Cz1+Cz2.....+Czz再+1 这个样子应该可以剪掉一部分枝吧
点赞 回复 分享
发布于 2019-07-27 21:03
暴力只能过25%啊
点赞 回复 分享
发布于 2019-07-27 21:00
同75%,也注意防止int溢出用了long long
点赞 回复 分享
发布于 2019-07-27 20:59

相关推荐

2025-12-08 16:04
门头沟学院 Java
本人本科末9,今年大三。大一大二一直玩,什么都没学到,在大学混日子混了两年,每天不是在打农就是在steam。大三开学时一个和自己玩的好的同学去实习了,才发现自己白白浪费了两年的时间,如果真不冲一下就真去京东,阿里,美团送外卖了今年9月份开始学Java,一开始一直跟着黑马视频看,后面发现看视频效率太低了,时间根本不够,就开始主要看文档和看书了。这几个月一直在学,真的尽力了,希望暑期前能找一份好点的实习。我简历上面的项目大多没有指标,但是实际上我是真没多少时间去做项目,我基本主要是动手只做了外卖和天机,黑马点评和12306我都是只是看了项目。主要是自己的时间真的不多,但是这样子自己的代码能力确实比较差。而且自己也没有做过实际的工程,我顶多用jmeter测试一下接口tps啥的,比如使用Redis管道提升了一点性能,减少Redis交互,这种值得写上去吗?需不需要具体到某些数字求求各位佬给一些建议,看看简历怎么优化?项目介绍是不是不够详细?没有具体到业务方面。项目会不会提到大致实现原理导致面试官一看简历就知道怎么实现就没有问的欲望?专业技能一些字段是不是要加粗,是不是写太啰嗦了?有没有必要压缩内容变成一页?两页的话是不是都要把两页填地满满的。
给秋招一个交代:一页简历最好,网上做的项目放面试官眼里都是玩具,简历上不需要强调有什么难点,记住就行防止真的问。然后背八股,多投多面试就行
点赞 评论 收藏
分享
评论
点赞
15
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务