파이썬에서 주어진 문자열을 빌드하기 위한 최소 비용을 결정하는 프로그램

길이가 n인 문자열 'str'을 작성해야 한다고 가정합니다. 문자열을 작성하기 위해 두 가지 작업을 수행할 수 있습니다.

• 비용을 지불하면 str 끝에 문자를 추가할 수 있습니다.
• substring sub_str은 비용 r의 str 끝에 추가할 수 있습니다.

문자열 str을 구축하는 데 필요한 최소 비용을 계산해야 합니다.

따라서 입력이 a =5, r =4, str ='tpoint'와 같으면 출력은 29가 됩니다.

문자열 'point'를 작성하기 위한 비용은 아래에 설명되어 있습니다. -

str ='t'; 새 문자가 추가되었으므로 비용은 5.str ='tp'입니다. 새 문자가 추가되었으므로 비용은 5.str ='tpo'입니다. 새 문자가 추가되었으므로 비용은 5.str ='tpoi'입니다. 새 문자가 추가되었으므로 비용은 5.str ='tpoint'입니다. 새 문자가 추가되었으므로 비용은 5.str ='tpoint'입니다. 하위 문자열 't'가 추가되므로 비용은 4입니다.

총 비용은 5 + 5 + 5 + 5 + 5 + 4 =29입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 크기 :=str의 크기
• 가장 큰 :=새 목록
• 낮음 :=0
• 범위 1에서 크기+1까지의 경우 다음을 수행합니다.
  • str[낮은 인덱스에서 높은 인덱스까지] str[인덱스 0에서 낮은 인덱스까지]에는 str[인덱스 0에서 낮은 인덱스까지]이 없지만, do
    • 낮음 :=낮음 + 1
  • 가장 큰 부분의 끝에 (upp - low) 삽입
• c :=다음을 포함하는 새 목록
• 범위 1에서 크기까지의 i에 대해
  • 최대[i]가 0과 같으면
    • c 끝에 삽입(c + a의 마지막 요소)
  • 그렇지 않으면
    • (c + a의 마지막 요소), (c[i - 가장 큰[i]] + r)의 최소값을 c 끝에 삽입
• c의 마지막 요소를 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(a, r, str):size =len(str) 최대 =[] low =0 for upp in range(1, size+1):str[low:upp]가 str[:low]:낮음 +=1 maximum.append(upp - low) c =[a] for i in range(1, size):if maximum[i] ==0:c.append(c[-1] + a ) else:c.append(min(c[-1] + a, c[i - 가장 큰[i]] + r)) return c[-1]print(solve(5, 4, 'tpoint')) 
입력
 
5, 4, '포인트'
 
출력
 
29