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

相关推荐

不愿透露姓名的神秘牛友
06-19 14:46
和女友两个人马上毕业,现在我在鹅实习995,周六日偶尔也去北京;她在北京金融007,经常忙到后半夜,周末也没啥休息机会两个人现在都不咋聊天了,一句话隔半小时甚至半天才回。&nbsp;她是个很优秀的妹子,工作也很努力,是值得学习一辈子的人。我在努力工作求转正,即便不行至少赚到了一段不错的实习经历。已经异地了半年,接下来可能还会持续是这个状态。我们都算是对方重要的人,只是感觉看上去不是很有未来的样子。希望牛友们给点的鼓励
梦旅奇缘:很难。异地首先就已经很难了,加上妹子是金融行业,忙碌高压,对情感需求很高,而且见惯纸醉金迷,你的很多优势在她那里可能就不算什么了。这种情况下,在她们那里遇到一个能及时照顾她的人,即使那人可能很多条件不如你,你也有可能被分手。 说白了,两个卷王就不太适合在一起。因为卷王最大的优势,在另一个卷王那里就不算优势了。
点赞 评论 收藏
分享
Twilight_mu:经典我朋友XXXX起手,这是那种经典的不知道目前行情搁那儿胡编乱造瞎指导的中年人,不用理这种**
点赞 评论 收藏
分享
求offer的大角牛:不吃香菜
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
15
分享

创作者周榜

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