120. 삼각형 최소 경로 와

삼각형 을 지정 하여 위 에서 아래로 의 최소 경로 와.한 걸음 한 걸음 은 다음 줄 에서 인접 한 결점 으로 만 이동 할 수 있다.
예 를 들 어 주어진 삼각형:
[[2], [3, 4], [6, 5, 7], [4, 1, 8, 3] 위 에서 아래로 의 최소 경로 와 11 (즉, 2 + 3 + 5 + 1 = 11).
설명:
만약 당신 이 O (n) 의 추가 공간 (n 은 삼각형 의 총 줄 수) 만 사용 하여 이 문 제 를 해결 할 수 있다 면, 당신 의 알고리즘 은 매우 가산 점 이 될 것 입 니 다.
재 귀 법: 만약 에 우리 가 숫자 를 모든 줄 의 아래 표 에 대응 하면 쉽게 발견 할 수 있 습 니 다. 하나의 data [i] [j] 에 대해 그 와 인접 한 숫자 는 data [i + 1] [j] 와 data [i + 1] [j + 1] 입 니 다.이렇게 되면 문 제 는 간단 해진 다.만약 에 우리 가 minimus [i] [j] 로 i 행 j 열 에 있 는 숫자 부터 마지막 층 까지 의 최소 경로 와...
minimus[i][j]=data[i][j]+min(minimums[i+1][j]+minimums[i+1][j+1])

func minimumTotal(triangle [][]int) int {

    if triangle == nil {
        return 0
    }
    return min2(triangle, 0, 0)
}

func min2(triangles [][]int, i int, j int) int {
    if i == len(triangles) {
        return 0
    }
    a := min2(triangles, i+1, j)
    b := min2(triangles, i+1, j+1)
    if a >= b {
        return triangles[i][j] + b
    }
    return triangles[i][j] + a
}

그러나 상기 설명 에는 O (n ^ 2) 의 추가 공간 이 필요 합 니 다. 다음은 이 문 제 를 해결 하 겠 습 니 다.
우 리 는 공식 적 으로 자식 문 제 를 재 귀적 으로 해결 해 야 하기 때문에, 우 리 는 거꾸로 생각해 보고, 먼저 자식 문 제 를 해결 한 후에 아버지 문 제 를 해결 하 는 것 도 괜찮다.즉, 아래 에서 위로 최소 경로 와.우 리 는 다음 과 같은 규칙 을 발견 할 수 있다. 우리 가 미니 엄 [i] [j] 을 풀 때 미니 엄 [i + 1] [j] 과 미니 엄 [i + 1] [j + 1] 을 사용 하지만 모든 미니 엄 [i] 을 풀 면 미니 엄 [i + 1] 은 쓸모 가 없다.그렇다면 우 리 는 같은 공간 을 재 활용 하여 minimum 의 값 을 저장 할 수 있 습 니까?답 은 돼.더 나 아가 마지막 줄 에 저 장 된 모든 숫자의 최소 경로 와 n 개의 공간 이 필요 하 다 는 것 을 발견 했다. 따라서 적어도 우 리 는 n 개의 공간 이 필요 하 다. 이것 도 문제 에서 O (n) 의 공간 복잡 도 를 제시 하 는 원인 이다.그 다음 에 마지막 두 번 째 줄 을 저장 할 때 우 리 는 앞의 n - 1 공간 만 필요 합 니 다.........................................................................
구체 적 인 산법 은 다음 과 같다.
알고리즘 설명 은 n 개의 공간 minNums [n] 를 신청 하고 minNums [n] 를 데이터 triangle [] [] 의 마지막 줄 로 초기 화 합 니 다.마지막 줄 의 숫자 가 맨 밑 에 있 는 가장 작은 경로 와 그들 자신 이다.마지막 두 번 째 줄 부터 위로 (row), 왼쪽 에서 오른쪽으로 (col) 순환 하여 minNums 의 값 을 계산 하고 업데이트 합 니 다. minNums [col] = min (minNums [col], minNums [col + 1] + triangle [row] [col] 마지막 minNums [0] 가 우리 가 원 하 는 답 입 니 다.

func minimumTotal(triangle [][]int) int {
    n := len(triangle)

    minNums := triangle[n-1]

    for i := n - 2; i >= 0; i-- {
        for j := 0; j <= i; j++ {
            if minNums[j] < minNums[j+1] {
                minNums[j] = minNums[j] + triangle[i][j]
            } else {
                minNums[j] = minNums[j+1] + triangle[i][j]
            }
        }
    }
    return minNums[0]
}