정수 삼각형

import java.util.*;
class Solution {
    public int solution(int[][] triangle) {
        
      for (int i = 1; i < triangle.length; i++) {
            triangle[i][0] += triangle[i-1][0];
            triangle[i][i] += triangle[i-1][i-1];
            for (int j = 1; j < i; j++) 
                triangle[i][j] += Math.max(triangle[i-1][j-1], triangle[i-1][j]);
        }
        
        int max = 0;
        for(int i = 0; i < triangle.length; i++) 
        max = Math.max(max, triangle[triangle.length - 1][i]);
    
        return max;
        
        }
        
    }

각 줄마다 맨 앞과 맨 뒤는 그 위에 있는 대각선위에 있는 것을 더해 준다. 가운데 있는 것은 최대값을 넣어줘야 한다. 예를 들어 [8 1 0] 3번째 줄에서 1은 max(7+3+1, 7+8+1) 해서 16이 된다. 이렇게 끝까지 내려가서 마지막줄에서 가장 큰 값을 리턴해주면 통과한다.