BOJ 17180 - 문자열 비교하기
단순히 편집거리처럼 풀어줄 수 있다.
$dp[i][j]$ 라면
- $dp[i-1][j-1] + \vert a[i]-b[j] \vert$
- $dp[i-1][j] + \vert a[i-1] - b[j] \vert$
- $dp[i][j-1] + \vert a[i] - b[j-1] \vert$
중 최소로 골라주면 된다.
첫 번째는 두 문자열에서 문자를 늘리지 않고 쓴것이고
두 번째는 $b$에서 문자를 늘린것이고
세 번째는 $a$에서 문자를 늘린것이다.
Comments