백준 9251: LCS( 최장공통 부분수열 / with Python)

dp[i][j]가 나타내는 것은, 문자열 1의 i번째까지의 부분 문자열과, 문자열 2의 j번째까지 부분 문자열을 비교했을 때의 최장 공통 부분수열이다.

 

이것을 생각하면, 12번 줄의 조건을 만족하여 dp[i][j]를 갱신할 때, 13번 줄처럼 dp[i-1][j-1]에 1을 더한다는 것을 쉽게 생각해낼 수 있을 것이다.