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##笔试题目#
小天才公司福利 1289人发布