2688번 줄어들지 않아

dp(n,k) -> n은 자리수, k는 n자리수 마지막 숫자를 의미한다.

 

그렇다면 n자리수에서 n-1자리수를 생각해보자. n-1개 자리수에서 마지막 한자리만 결정해주면 n개 자리수를 구할 수 있다.

 

n자리수가 0으로 끝나면 n-1자리수는 0으로 끝나야 한다.

n자리수가 1로 끝나면 n-1자리수는 0과 1이 올 수 있다.

 

즉, dp(n,k)는 dp(n-1,k보다 작거나 같은 수)이며 이를 다 합하면 dp(n,k)의 개수가 된다.

 

추가. memset 대신 메모이제이션을 이용하면 시간을 줄일 수 있다. (if(dp[i][j]>0) continue; 하면 되지 않을까 싶다)