최장증가수열 1편 가장 기초 (역추적 x), 백준 가장 긴 증가하는 부분 수열

문제

https://www.acmicpc.net/problem/11053

문제 설명

• dp[i]는 i번째 위치일 때 가장 긴 수열의 길이

• dp[i] = max(dp[i], dp[j] + 1)이다 왜냐 ? 왜 dp[i]가 있냐면 x1 x2 x3 x4.. 이렇게 있을 때, x4가 x1 -> x4일 수도 있고, x1 x2 x4가 될 수도 있기때문에 계속해서 dp[i]는 갱신되어야한다
• 그리고 또한 마지막에 모든 부분에서 dp[i]를 찾는 것도 위의 이유이기도하고 마지막 위치 dp[n]을 출력하지 않는 이유는 만약 n번째를 가지못한다면 어떻게 할 것인가? -> 1 2 3 2 이렇게 되면 마지막에는 도달 하지못한다...

소스

#include <bits/stdc++.h>

using namespace std;

int n;
int a[2000];
int dp[2000];
//dp[i] = i번재 위치를 볼때 가장 긴 값 
//dp[i] = max(dp[i], dp[j] + 1)  max안에 dp[i]도 넣는이유는   x1 x2 x3 x4..가 있을때 x4를 볼때 x1 x2 x4로 올 수도 있고, x1 x4로 바로 올 수도 있기때문에 갱신을 해주어야한다 

int main() {

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    memset(dp, -1, sizeof(dp));

    dp[0] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (j < i && a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, dp[i]);
    }
    cout << ans;
    return 0;
}