ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 9251
    알고리즘/acmicpc 2015. 2. 17. 17:18

    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])


    요렇게

    '알고리즘 > acmicpc' 카테고리의 다른 글

    1958  (0) 2015.02.17
    9252  (0) 2015.02.17
    9251  (0) 2015.02.17
    2599  (0) 2015.02.15
    2436  (0) 2015.02.15
    2533  (0) 2015.02.14

    댓글 0

Designed by Tistory.