Sum Decomposition-Advanced Solution

2차원 DP -> 1차원 DP

2차원 DP를 1차원으로 줄임으로써 시간, 공간 자원을 절약할 수 있다!

2차원 => 1차원 변환 과정

• 시간, 공간 복잡도 계산

1. 2차원 DP의 시간 복잡도 : i -k번, j-n번, l-j(n)번 = O(kn^2)

for(int i= 1;i<=k;i++) {
		for(int j= 0;j<=n;j++) {
				for(int l=0;l<=j;l++) {//l<=j
					d[i][j] += d[i-1][j-l];
					d[i][j] %= mod;
				}
		}
	}

2. 1차원 DP의 시간 복잡도 : i-k번, j-n번 = O(kn)

for(int i=1;i<=k;i++) {
		for(int j=1;j<=n;j++) {
				d[j] += d[j-1];
				d[j] %= mod;
		}
}

실제로 실행시간과 메모리도 줄어든 걸 확인할 수 있다.

시간, 메모리 차이