[programmers]整数三角形-ダイナミックプランニング

// 정수 삼각형 - 동적계획법(Dynamic Programming)
public class IntegerTriangle {
	
	/*
	 *               7
	 *              3 8
	 *             8 1 0
	 *            2 7 4 4
	 *           4 5 2 6 5    
	 *                        => 맨아래 4 와 5 중 큰 값을 그 위에 2와 더함, 5 와 2 중 큰 값을 그 위에 7과 더함, 2 와 6 중 큰 값을 그 위에 4와 더함, 6 과 5 중 큰 값을 그 위에 4와 더함
	 *                        => 위 층으로 올라가면서 반복
	 *                        => 맨 꼭대기 값을 리턴                          
	 */
	
	public int solution(int[][] triangle) {
		for (int i = triangle.length - 2; i >= 0; i--) {
			for (int j = 0; j < triangle[i].length; j++) {
				triangle[i][j] += Math.max(triangle[i + 1][j], triangle[i + 1][j + 1]);
			}
		}
		return triangle[0][0];
	}
}