[Baekjoon - 22971] 증가하는 부분 수열의 개수

난이도: Silver II

 

태그

• Dynamic Programming
  • Longest Increasing Subsequence

 

풀이

1. DP 세우기

\( dp_{i} \) = \( i \)번째 원소를 끝으로 하는 LIS의 개수 를 정의해봅시다.

 

초항은 \( dp_{0} = 1 \)입니다.

점화식은 어떨까요?

 

\( A_{j} < A_{i} \)인 모든 \( j \)에 대해, \( [\ldots, A_j, A_i] \)의 수열을 만들 수 있으므로

\( dp_{i} = \sum\limits_{j<i \text{ and } A_j < A_i} dp_{j} \)가 됩니다.

 

2. 코드

const ll mod = 998244353;
int arr[5020];
ll dp[5020];
 
void Main(){
    int n; cin >> n;
    for (int i = 1; i <= n; i++){ cin >> arr[i]; }
    dp[0] = 1; for (int i = 1; i <= n; i++){
        for (int j = 0; j < n; j++){
            dp[i] += (arr[j] < arr[i])*dp[j];
            dp[i] %= mod;
        }
        cout << dp[i] << ' ';
    }
}