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##笔试题目#