정수 삼각형

사용 알고리즘: DP

사용 언어: java

 

 

import java.util.*;
import java.io.*;

class Solution {
    public int solution(int[][] triangle) {
        int len = triangle.length;
        int[][] dp = new int[len][len];
        
        dp[0][0] = triangle[0][0];
        for(int i=1; i<len; i++){
            for(int j=0; j<=i; j++){
                dp[i][j] = triangle[i][j];
                if(j==0)  
                    dp[i][j] += dp[i-1][j];
                else{
                    dp[i][j] += Math.max(dp[i-1][j], dp[i-1][j-1]);
                }
            }
        }
        
        int answer = 0;
        for(int i=0; i<dp[len-1].length; i++) {
            answer = Math.max(answer, dp[len-1][i]);
        }
        return answer;
    }
}

 

 

dp 기본형