값 n과 cuts라는 배열이 있다고 가정합니다. 길이가 n 단위인 나무 막대기가 있다고 가정합니다. 스틱은 0에서 n까지 레이블이 지정됩니다. 여기에서 cut[i]는 우리가 자를 수 있는 위치를 나타냅니다. 컷은 순서대로 진행해야 하지만 컷의 순서는 원하는 대로 변경할 수 있습니다. 여기서 한 컷의 비용은 절단할 막대의 크기이고 총 비용은 모든 컷의 비용 합계입니다. 우리는 삭감의 최소 총 비용을 찾아야 합니다.
따라서 입력이 n =7, cuts =[5,1,4,3]과 같으면 출력은 16이 됩니다. 왜냐하면 [3,5,1,4]와 같이 주문하면 처음에는 길이 7에서 3이므로 비용은 7이고 길이 3과 4의 두 부분이 있고 5에서 자르므로 비용은 4입니다. 지금까지 총계는 7+4=11이고 스틱 크기 2에서 4로 잘라냅니다. , 따라서 총 비용 7+4+2 =13, 마지막으로 3에서 잘라 비용이 3이 되고 최종 비용이 7+4+2+3 =16이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
cuts :=cuts의 요소가 정렬된 순서로 있는 목록, 시작 부분에 0, 끝 부분에 n 삽입
-
m :=절단 크기
-
비용 :=m x m 크기의 정방 행렬을 만들고 0으로 채움
-
범위 2에서 m - 1까지의 k에 대해 수행
-
0 ~ m - 1 범위의 i에 대해 수행
-
j :=i + k
-
j>=m이면
-
다음 반복으로 이동
-
-
비용[i, j] =(cuts[j] - cuts[i]) + 범위(i+1, j-1)의 모든 s에 대한 (비용[i, s] + 비용[s, j]의 최소값)
-
-
반품 비용[0, m-1]
-
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
def solve(n, cuts): cuts = [0] + sorted(cuts) + [n] m = len(cuts) cost = [[0]*m for _ in range(m)] for k in range(2, m): for i in range(m): j = i + k if j >= m: continue cost[i][j] = (cuts[j]-cuts[i]) + min(cost[i][s] + cost[s][j] for s in range(i+1, j)) return cost[0][m-1] n = 7 cuts = [5,1,4,3] print(solve(n, cuts))
입력
7, [5,1,4,3]
출력
16