동적 계획 - 구간 모델: 최소 문 자 를 추가 하여 문자열 을 답장 문자열 로 변경 합 니 다.

5010 단어 알고리즘
문제: (하나의 문자열 이 읽 고 있 는 것 과 거꾸로 읽 는 것 이 같 으 면 답장 문자열 이 라 고 합 니 다) 문자열 s 를 지정 하고 s 의 임 의 위치 에 임 의 문 자 를 추가 합 니 다. 최소 몇 개의 문 자 를 추가 하면 s 를 답문 문자열 로 바 꿀 수 있 습 니까?
예제 1: 문자열 "ab", 최소 1 글자 "b" 를 추가 하여 답장 문자열 "bab" 로 바 꿉 니 다.
예제 2: "a", 최소 0 자 를 추가 하여 답장 문자열 "a" 로 바 꿉 니 다.
예제 3: "abca" 최소 1 글자 추가 "b" 를 답장 문자열 "abcba" 로 바 꿉 니 다.
예시 4: "abcd" 최소 3 개의 문 자 를 추가 하면 답장 문자열 로 변 합 니 다 "adbcbda"
동적 계획 구간 모델 을 이용 하여 설명:
def text(s=""):
    n = len(s)
    db = [[0 for _ in range(n)] for __ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if i == j:
                db[i][j] = 0
            elif s[i] == s[j]:
                db[i][j] = db[i + 1][j - 1]
            else:
                db[i][j] = min(db[i + 1][j], db[i][j - 1]) + 1
    return db[0][-1]
사지 수 알고리즘 원리 와 실현
[가방 + DP] 가방 문제 + 면접 실례

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage