[프로그래머스] 정수삼각형 -DP JAVA [자바]

DP(기억하며 푸는 알고리즘)

메모리를 사용해서 중복 연산을 줄이고 중복 연산을 줄여서 수행 속도를 개선한다.

풀이과정:

DFS/BFS로 풀 수 있지만 경우의 수가 너무 많은 문제

5줄짜리 삼각형이라면 DFS로 풀어도 괜찮지만 500줄 삼각형이라면 경우의 수가 많이 지장이 생긴다.

최적의 조합을 dp배열에 넣기 찾아 갱신하기

코드

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int height = triangle.length;
        int [][]dp = new int[height][height];

        //왼쪽
        dp[0][0] = triangle[0][0];
        for(int i = 1; i < height; i++) {
            dp[i][0] = dp[i-1][0] + triangle[i][0];
        }
        
        
        for(int i = 1; i < height; i++) {
            for(int j = 1; j <= i; j++) { // 삼각형 형태의 배열 구조로 i까지
            dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j];
            }
        }
        
        //마지막 줄에서 가장 높은 값
        for(int i = 0 ; i < height; i++) {
            answer = Math.max(dp[height - 1][i], answer);
        }
        
        return answer;
    }
}

개취 유튜브 - 풀이영상