백준 16474 : 이상한 전깃줄(DP, LIS)

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

16474번: 이상한 전깃줄

풀이
본인은 LIS로 접근하지 못해서 DP로 접근함
DP[n][m]=왼쪽 n번째 전봇대와 m번째 전봇대를 이으려 할때 연결 가능한 최대 전깃줄 수

만약 n->m으로 연결하는 전깃줄이 있을 경우
DP[n][m]=max(DP[n-1][m-1]+1, DP[n-1][m])
전깃줄이 없을 경우는

DP[n][m]=max(DP[n-1][m],DP[n][m-1])

시간복잡도 : O(n * m) , n , m <=2000

#include<bits/stdc++.h>
#include<time.h>


#define MAX 1000000007
#define INF 2000000000
#define MOD 1000000007 
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

int dx[8] = { 0, -1, 0, 1, 1, 1, -1, -1 };
int dy[8] = { -1, 0, 1, 0, -1, 1, 1, -1 };

/*
int dx[2][6] = {
    {1, -1, 0, 0 ,1, -1},
    {1, -1, 0, 0, -1, 1}
};
int dy[2][6] = {
    {0, 0, 1, -1 ,1, -1},
    {0, 0, 1, -1, 1, -1}
};*/

//int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
//int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }

int left_idx[2001];
int right_idx[2001];

int dp[2001][2001];
int main() {
    init();
    int n, m; cin >> n >> m;
    int num;
    for (int i = 1; i <= n; i++) {
        cin >> num;
        left_idx[num] = i;
    }
    for (int i = 1; i <= m; i++) {
        cin >> num;
        right_idx[num] = i;
    }
    int k; cin >> k;
    for (int i = 0; i < k; i++) {
        int a, b; cin >> a >> b;
        dp[left_idx[a]][right_idx[b]] = 1;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = max(dp[i - 1][j], max(dp[i - 1][j - 1] + dp[i][j], dp[i][j - 1]));
        }
    }
    cout << k - dp[n][m] << "\n";
}