[백준 9251] LCS

[BanApp]

arr1 = list(input())
arr2 = list(input())

tmp = [[0]*(len(arr2)+1) for _ in range((len(arr1))+1)]

for i in range(len(arr1)):
    for j in range(len(arr2)):
        if arr1[i] == arr2[j]:
            tmp[i+1][j+1] = tmp[i][j] +1
        else:
            if tmp[i][j+1] >= tmp[i+1][j]:
                tmp[i+1][j+1] = tmp[i][j+1]

            elif tmp[i][j+1] < tmp[i+1][j]:
                tmp[i+1][j+1] = tmp[i+1][j]

print(tmp[len(arr1)][len(arr2)])

아이디어는 우선 두개의 리스트의 원소를 각각 비교해주는것은 불피하다.
따라서 시간복잡도는 O(NM)이다.
우선 arr1[I] == arr2[j]를 만족하면 대각선 밑에 있는것을 1 증가 시킨다.
왜그러냐면 조합상 arr[0][0] ~ arr[i+1][j+1] 사이에서 만들 수 있는 가장 긴 LCS 크기는 위 조건을 만족할때 arr[i][j] + 1 이기 때문이다.
원소가 같지 않을때는 arr[i-1][j] 와 arr[I][j-1] 중 더 큰것으로 한다.
이 과정에서 인덱스 에러를 피하기 위해서 0으로 이차원 리스트의 왼쪽과 상단을 0으로 감싸준다.
이를 반복하면 가장 오른쪽 최하단에 있는 숫자가 두개의 리스트에서 만들어 질 수 있는 가장 긴 LCS의 값이 나온다.

이런식으로 말이다.

사실 뭔가 수학적으로 이해했기 보다는 직접 그려서 규칙을 찾는 식으로 진행했다.
아이디어만 떠올리면 쉽지만 그게 어려운 DP...
그래도 DP문제는 어떻게든 이전 값을 써먹으려는 방향으로 점화식을 고민하다보면 결국 답은 나온다.

[3316891527]

感谢详细的建议和完整的源码补丁。我们已经仔细审阅了你提供的方案。

我们目前的规划是优先推进一个更完整的浮窗小部件系统（已有 PoC 实现），该系统不仅可以提供包括头像状态、动态反馈等交互体验，还支持：

• 跨应用浮窗显示（不受聊天界面限制）
• 丰富的交互方式（拖拽、点击、长按等）
• 实时状态同步和动态更新
• 资源热更新（无需重新编译 App）
• 插件化扩展机制

相比单纯在聊天气泡内增加头像动作，浮窗方案在功能完整性、交互灵活性和维护成本上都更具优势。我们认为这个方向能更好地满足未来的交互需求。

你的补丁实现思路清晰、测试完整，如果后续有其他类似的功能建议，欢迎继续提交～