좋은 문자열을 만드는 방법 계산

2466. 좋은 현악기를 만드는 방법을 세어보세요

난이도:중

주제: 동적 프로그래밍

0, 1, low, high 정수가 주어지면 빈 문자열로 시작하여 문자열을 구성한 후 각 단계에서 다음 중 하나를 수행할 수 있습니다.

• '0' 문자를 0번 추가하세요.
• '1' 문자를 1번 추가하세요.

이 작업은 여러 번 수행할 수 있습니다.

좋은 문자열은 위의 프로세스를 통해 생성된 문자열로, low와 high 사이(포함)의 길이를 갖습니다.

이러한 속성을 만족하도록 구성할 수 있는 다양한 좋은 문자열의 개수를 반환합니다. 답이 클 수 있으므로 모듈로 10⁹ 7.

반환하세요.

예 1:

• 입력: 낮음 = 3, 높음 = 3, 0 = 1, 1 = 1
• 출력: 8
• 설명:
  • 가능한 유효한 양호한 문자열 중 하나는 "011"입니다.
  • 다음과 같이 구성할 수 있습니다: "" -> "0" -> "01" -> "011".
  • 이 예에서는 "000"부터 "111"까지의 모든 이진 문자열이 좋은 문자열입니다.

예 2:

• 입력: 낮음 = 2, 높음 = 3, 0 = 1, 1 = 2
• 출력: 5
• 설명: 좋은 문자열은 "00", "11", "000", "110" 및 "011"입니다.

제약조건:

• 1

  설명:

  1. 초기화: 기본 사례 dp[0] = 1로 설정하여 시작합니다. 즉, 길이가 0인 문자열(빈 문자열)을 형성하는 한 가지 방법이 있음을 의미합니다.
  2. 동적 프로그래밍 업데이트: 1부터 높은 각 문자열 길이에 대해 길이가 0 또는 1인 문자열을 더 작은 문자열에 추가할 수 있는지 확인합니다. 길이가 i-0과 i-1인 문자열을 형성하는 방법의 수를 추가하여 dp[i]를 업데이트하여 결과가 모듈로 10⁹ 7.
  3. 최종 결과 계산: 유효한 문자열의 최종 개수를 얻기 위해 [low, high] 범위에 있는 i에 대한 dp[i]의 모든 값을 합산합니다.
  시간 복잡도:
  dp 배열을 채우는 데는 O(높음)이 걸립니다.
  낮음과 높음 사이의 유효한 결과를 합산하려면 O(높음 - 낮음 1)가 필요합니다.
  따라서 전체적인 시간복잡도는

  ** O(high) **로, 입력한계에 충분히 효율적입니다.

  공간 복잡도:
  high 1 크기의 dp 배열을 사용하므로 공간 복잡도는
  • O(high)입니다.
  이 솔루션은 제약 조건 내에서 문제를 효율적으로 해결합니다.

  연락처 링크

  이 시리즈가 도움이 되었다면 GitHub에서

  저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

  이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.
  • 링크드인
  • 깃허브

위 내용은 좋은 문자열을 만드는 방법 계산의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!