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

相关推荐

04-06 11:24
已编辑
太原学院 C++
点赞 评论 收藏
分享
独玖:同二本,建议咱俩一起重开
点赞 评论 收藏
分享
评论
点赞
15
分享

创作者周榜

更多
牛客网
牛客企业服务