*Triangle
3856 단어 RIA
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is
11 (i.e., 2 + 3 + 5 + 1 = 11). Note:Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
문제:
동적 기획의 고전적인 제목밑바닥에서 위로 해답을 구해야 한다.
점차적인 공식은 dp[i][j]=dp[i+1][j]+dp[i+1][j+1]이다. 현재 이 점의 최소값은 그의 아래 줄에 가까운 두 점의 최소값과 현재 점의 값을 더한다.
삼각형이고 역사 데이터는 최소 값을 계산할 때 한 번만 적용되기 때문에 2차원 그룹을 만들 필요가 없다. 1차원 그룹의 값을 업데이트할 때마다 마지막으로 그 값에 저장된 것이 최종 결과이다.
코드는 다음과 같습니다.
1 public int minimumTotal(List<List<Integer>> triangle) {
2 if(triangle.size()==1)
3 return triangle.get(0).get(0);
4
5 int[] dp = new int[triangle.size()];
6
7 //initial by last row
8 for (int i = 0; i < triangle.get(triangle.size() - 1).size(); i++) {
9 dp[i] = triangle.get(triangle.size() - 1).get(i);
10 }
11
12 // iterate from last second row
13 for (int i = triangle.size() - 2; i >= 0; i--) {
14 for (int j = 0; j < triangle.get(i).size(); j++) {
15 dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
16 }
17 }
18
19 return dp[0];
20 }Reference: http://www.programcreek.com/2013/01/leetcode-triangle-java/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
zoj1245Triangles이 문제는 어렵지 않다. 단지 귀속을 한 번 썼을 뿐이지만, 문자열 처리에 있어서는 중간에 많은 작은 세부 사항을 주의해야 한다. 사고방식은 매우 간단하다. 모든 흰색의 삼각형에 대해 먼저 입구가 위로 향하는지 아래...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
