동적 계획 LeetCode 120. 삼각형 최소 경로 와
삼각형 을 지정 하여 위 에서 아래로 의 최소 경로 와.한 걸음 한 걸음 은 다음 줄 에서 인접 한 결점 으로 만 이동 할 수 있다.
예 를 들 어 주어진 삼각형:
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
위 에서 아래로 최소 경로 와 위
11
+ 3 + 5 + 1 = 11)。 설명:
하면, 만약, 만약... O(n) 추가 공간 삼각형 의 총 줄 수 를 위해) 이 문 제 를 해결 하면 당신 의 알고리즘 은 매우 가산 점 을 줄 것 입 니 다.
class Solution {
public int minimumTotal(List> triangle) {
int[][] res = new int[triangle.size()][triangle.size()];// List
//
int[][] dp = new int[triangle.size()][triangle.get(triangle.size() - 1).size()];
int i = 0, j = 0;
for (List a : triangle) {
j = 0;
for (Integer b : a) {
res[i][j++] = b;
}
i++;
}
// , ,
//
for (int a = 0; a < res[res.length - 1].length; a++) {
dp[res.length - 1][a] = dp[res.length - 1][a] + res[res.length - 1][a];
}
//
for (int a = res.length - 2; a >= 0; a--) {
for (int b = 0; b < res[a].length - 1; b++) {
dp[a][b] = Math.min(dp[a + 1][b], dp[a + 1][b + 1]) + res[a][b];
}
}
for (int a = 0; a < triangle.size(); a++) {
for (int b = 0; b < triangle.get(a).size(); b++) {
System.out.print(dp[a][b] + " ");
}
System.out.println();
}
return dp[0][0];
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.