120. Triangle(삼각형 최소 경로 및)
1275 단어 Leetcode
아이디어:
DP로 해결하고 2차원 배열을 쓰려고 했는데 한 배열 역시 가능하다는 걸 알게 됐다.
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]이런 것은 다음과 같이 이해할 수 있다.
2
3 4
6 5 7
4 1 8 3
list 하위 표시, 즉 현재 줄의 i번째 하위 표시에 대응하고 다음 줄의 i와 i+1만 사용할 수 있습니다.
그래서 우리는 아래에서 위로 해답을 구할 수 있다.
DP의 핵심은 재사용 가능한 하위 구조를 찾아내는 것입니다.
A[j]=Math.min(A[j],A[j+1])+triangle.get(i).get(j);
구체적인 예는 다음과 같다.
i=3 :A[4 1 8 3] 0; 이 교체 전 A[j]의 요소는 모두 0이기 때문에 Triangle에 대응합니다.get(i).get(j)의 값입니다.
i=2 : A[7 6 10] 3 0; 이전 레이어에서 Math를 선택합니다.min(A[j], A[j+1])로 A[j] 업데이트
i=1 :A[9 10] 10 3 0;
i=0 :A[11]10 10 3 0;
대괄호 뒤에 있는 요소는 현재 레이어에서 더 이상 사용되지 않는 부분입니다.
성명 수조가 크기가 크기보다 1시간이 많은 것은 A[j+1]를 구할 때 수조가 경계를 넘는 상황을 방지하기 위해서이다.
AC 1ms 99.9% Java:
class Solution {
public int minimumTotal(List> triangle) {
int[] A=new int[triangle.size()+1];
for(int i=triangle.size()-1;i>=0;i--){
for(int j=0;j<=i;j++){
A[j]=Math.min(A[j],A[j+1])+triangle.get(i).get(j);
}
}
return A[0];
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode 문제풀이 노트 113.경로 총 II경로 총 II 제목 요구 사항 문제풀이 두 갈래 나무와 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾는 것은 목표와 같은 경로입니다. 설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다. 예: 다음과 같은 두 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
