Dynamic Programming

Longest Common Subsequence
맨 뒤부터 본다.
L1, L2가 있으면 L1[n]과 L2[m]을 비교한다.
같으면 길이를 1 추가하고 L1[n-1] L2[m-1]을 비교하고,
다르면 max(L1[n-1]L2[m] , L1[n]L2[m-1])을 구한다.


Longest Increasing Subsequence
숫자들로 이뤄진 리스트가 있고 그중에서 longest subsequence를 찾는데 그 subsequence는 ascending order로 정렬돼있어야한다.
리스트의 길이만큼 다른 리스트 L2를 만들어서 그 리스트의 i번째에는 숫자 리스트의 i번째까지의 LIS 길이가 저장된다.
그러면 L2[0]에는 1이 저장된다.
어떤 시점에 보고 있는 i번째 L[i]에는 L2[0] ~ L2[i-1]중에서 numbers[i]보다 작은 값을 가지는 것들 중에 최댓값+1이 들어간다.



Edit Distance
string 두 개가 주어지고 insert, remove, replace의 작업을 str1에 할 수 있을 때 몇 번의 최소 작업으로 str2와 같아지는 지 구해야 한다.
맨 뒤부터 비교를 한다. 두 문자가 같으면 str1[n-1] str2[m-1]을 recursive하게 부른다.
다르면 insert, remove, replace 세 가지 경우를 다 고려한다.
insert를 하고 str1[n] str[m-1]를 한 경우, remove하고 str1[n-1] str2[m]을 한 경우, replace를 하고 str[n-1] str[m-1]을 한 경우 중 최소를 구한다.
dp[n][m]에 각각의 결과를 저장함으로써 시간을 줄인다.



Longest Path in Matrix
숫자들로 채워진 matrix가 있고 그중에서 원소 값이 1씩 증가하면서 이을 수 있는 가장 긴 path를 찾아야 한다.
전체 원소에 대해서 왼, 오, 위, 아래 모두 탐색해가며 그중 가장 큰 값을 다른 행렬에 저장한다.
어떤 위치에 대해 최댓값이 저장돼있다면 사방을 탐색할 필요 없이 그 값을 리턴한다.
모든 원소에 대해 이 작업을 하고 나면 저장된 값들 중 가장 큰 값을 리턴한다.