N 門課,最多 M 天。第 i 門課花 j 天獲得收益 A[i][j]。每門課**恰好選擇一種**天數(或 0 天),總天數 ≤ M,最大化總收益。
這是**分組背包**(每組必選一項)或**多重選擇背包**問題。
`dp[i][j]`:前 i 門課用 j 天的最大收益。
轉移:`dp[i][j] = max(dp[i-1][j-k] + A[i][k])` for k=0..j(k=0 表示不選這門課)。
int dp[101] = {0};
for (int i = 1; i <= N; i++) {
for (int j = M; j >= 0; j--) {
for (int k = 1; k <= j; k++) {
dp[j] = max(dp[j], dp[j-k] + A[i][k]);
}
}
}
answer = dp[M];