. 이상한 프린터

664. 이상한 프린터

난이도:어려움

주제:문자열, 동적 프로그래밍

다음 두 가지 특별한 속성을 가진 이상한 프린터가 있습니다:

• 프린터는 매번동일한 문자의 순서만 인쇄할 수 있습니다.
• 각 차례마다 프린터는 어떤 위치에서 시작하고 끝나는 새 문자를 인쇄할 수 있으며 원래의 기존 문자를 덮을 것입니다.

문자열 s가 주어지면프린터가 인쇄하는 데 필요한 최소 회전 수.

를 반환합니다.

예 1:

• 입력:s = "aaabbb"
• 출력:2
• 설명:먼저 "aaa"를 인쇄한 다음 "bbb"를 인쇄합니다.

예 2:

• 입력:s = "aba"
• 출력:2
• 설명:먼저 "aaa"를 인쇄한 다음 문자열의 두 번째 위치부터 "b"를 인쇄합니다. 이는 기존 문자 'a'를 덮습니다.

제약조건:

• 1 <= s.length <= 100
• s는 영문 소문자로 구성됩니다.

해결책:

동적 프로그래밍을 사용할 수 있습니다. 문자열을 하위 문제로 나누어 인쇄하는 데 필요한 회전 수를 최소화하는 것이 아이디어입니다.

동적 프로그래밍을 사용하면 문제를 해결할 수 있습니다. 아이디어는 s의 모든 하위 문자열을 인쇄하는 데 필요한 최소 회전 수를 결정하는 더 작은 하위 문제로 문제를 나누는 것입니다. 우리는 다음 관찰을 활용할 수 있습니다:

• 인접한 두 문자가 동일한 경우 새 작업으로 계산하는 대신 이전 작업을 확장할 수 있습니다.

동적 프로그래밍 솔루션

dp[i][j]를 하위 문자열 s[i:j+1]을 인쇄하는 데 필요한 최소 회전 수로 설정합니다.

1. If s[i] == s[j]이면 dp[i][j] = dp[i][j-1]입니다. 이전 작업으로 마지막 문자 s[j]를 인쇄할 수 있기 때문입니다.
2. 그렇지 않으면 dp[i][j] = min(dp[i][k] + dp[k+1][j]) 모든 i <= k < j.

이 솔루션을 PHP로 구현해 보겠습니다:664. 이상한 프린터

으아악

설명:

1. DP 배열:2D 배열 dp[i][j]는 인덱스 i에서 j로 하위 문자열을 인쇄하는 데 필요한 최소 회전 수를 나타냅니다.

2. 초기화:한 번에 한 문자를 인쇄할 수 있기 때문에 dp[i][i] = 1로 초기화합니다.

3. DP 테이블 채우기:

   • i와 j의 문자가 동일한 경우($s[$i] == $s[$j]), i에서 j로 인쇄하는 데는 i에서 j로 인쇄하는 것과 동일한 회전 수가 걸립니다. $s[$j]는 $s[$i]와 같은 차례에 인쇄될 수 있으므로 1입니다.
   • 다르면 끈을 서로 다른 지점(k)으로 나누어 최소 회전 수를 구합니다.

4. 결과:전체 문자열을 인쇄하는 데 필요한 최소 회전 수는 dp[0][$n - 1]에 저장됩니다.

   # #

이 솔루션은 문자열을 분할하여 인쇄할 수 있는 모든 방법을 고려하여 문자열 인쇄에 필요한 최소 회전 수를 효율적으로 계산합니다.

연락처 링크

이 시리즈가 도움이 되었다면

repository에 별점을 주거나 좋아하는 소셜 네트워크에 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요:

• LinkedIn
• GitHub

위 내용은 . 이상한 프린터의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!