POJ 디지털 조합

배낭 문제와 유사하니 이 문제는 문제에서 분명하게 설명하지 못했음을 주의해라. 예를 들어 N=3, T=4 2 22 2의 경우 답은 세 가지이다.

#include
using namespace std;
//   n          T
int dp[30][1010];//dp[i][j]   i            j 
int n,t,num[30],ans;

int main() {
	cin>>n>>t;
	for(int i=1; i<=n; i++) cin>>num[i];
	for(int i=0;i<=n;i++) dp[i][0]=1; //      1 0，    j-num[i]==0 ，          j 
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=t; j++) {
			if(j>=num[i]) dp[i][j]=dp[i-1][j]+dp[i-1][j-num[i]];//     i   
			else dp[i][j]=dp[i-1][j];
		}
	}
	cout<<dp[n][t];
}

공간 복잡성 최적화:

#include
using namespace std;

int dp[1010];//dp[i][j]   i            j 

int n,t,num[30];

int main() {
	cin>>n>>t;
	for(int i=1; i<=n; i++) cin>>num[i];
	dp[0]=1; 
	for(int i=1; i<=n; i++) {
		for(int j=t; j>=1; j--) {
			if(j>=num[i]) dp[j]=dp[j]+dp[j-num[i]];
			else dp[j]=dp[j];
		}
	}
	
	cout<<dp[t];
}