Leetcode 삼각형 문제 풀이 보고서
http://oj.leetcode.com/problems/triangle/
동적 계획 의 전형 적 인 문제 인 POJ 1163 도 같은 유형 문제 로 유일한 차이 점 은 Leetcode 가 최소 치 를 구하 고 POJ 1163 이 최대 치 를 구 하 는 것 이다.
전달 공식 이 관건 이다. 원 배열 이 수정 된다 고 가정 하면 전달 공식 은 array [i] [j] = array [i] [j] + Math. max (array [i - 1] [j - 1], array [i - 1] [j]) 이다.
위 에서 아래로 모든 경로 의 최소 치 는 상부 의 두 인접 노드 에 의 해 결정 된다.
아래 에서 위로 계산 하면 국경 문 제 를 적 게 고려 할 수 있다.
POJ 1163 AC 의 코드 는 다음 과 같다.
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int count = scan.nextInt();
int [][] array = new int [count][count];
for(int i=0;i1) {
for(int i=count-2;i>=0;i--) {
for(int j=0;j Leetcode Triangle AC 의 코드 는 다음 과 같 습 니 다.
public class Solution {
public int minimumTotal(ArrayList> triangle) {
// Start typing your Java solution below
// DO NOT write main() function
for(int i = triangle.size() - 2; i >= 0; i--)
{
for(int j = 0; j < triangle.get(i).size(); j++)
{
triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)));
}
}
return triangle.get(0).get(0);
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
