9251

LCS문제

모두의 부부수열이 되는 수열중 가장긴것을 찾는문제

전형적인 dp문제인데 이때 d배열을 2차원으로 해야한다는 점이 중요

점화식만 잘 만들면 어렵지 않게 해결 할 수 있다.

현재 위치의 dp값을 지정해주려면

if(A[i] == B[i]) dp[i][j] = max(dp[i-1][j-1] + 1, dp[i-1][j], dp[i][j-1])

else dp[i][j] = max(dp[i][j-1], dp[i-1][j])

요렇게