dp[i][j]: the number of subsets of A[0, i] whose sum is j.
dp[0][0] = 1, there is only 1 way of not picking anything from an empty array to achieve sum 0.
Answer is dp[N][S]
State Transition:
case 1, not using A[i] : all the subsets of A[0, i - 1] are also subsets of A[0, i], so dp[i][j] += dp[i - 1][j] * 2;
case 2, using A[i], dp[i][j] += dp[i - 1][j - A[i]];
static void solve(int testCnt) { for (int testNumber = 0; testNumber < testCnt; testNumber++) { int n = in.nextInt(), s = in.nextInt(), mod = 998244353; int[] a = in.nextIntArrayPrimitiveOneIndexed(n); long[][] dp = new long[n + 1][s + 1]; dp[0][0] = 1; for(int i = 1; i <= n; i++) { for(int j = 0; j <= s; j++) { dp[i][j] = addWithMod(dp[i][j], dp[i - 1][j] * 2, mod); if(j >= a[i]) { dp[i][j] = addWithMod(dp[i][j], dp[i - 1][j - a[i]], mod); } } } out.println(dp[n][s]); } out.close(); }
标签:AtCoder,subsets,Subsets,int,testNumber,nextInt,Knapsack,dp,out From: https://www.cnblogs.com/lz87/p/17139523.html