사용한 알고리즘 : 동적 계획법

---

해당문제는 꼭대기에서 부터 내려가며 해결하는 방법보다는
top - down
바닥에서 꼭대기로 올라가면서 해결을 하는것이 좋아보였다
Bottom - up

---

📌 변수 초기화

• 삼각형 배열의 길이(삼각형의 높이) 를 담을 변수 n
• 각 위치의 최대 합을 저장할 dp 배열

int n = triangle.length;
int[][] dp = new int[n][n];

---

📌 dp 배열 초기화

• 삼각형의 마지막 줄을 dp의 마지막 줄에 복사
• 각 위치에서 최대합을 계산하기 위한 시작점이 되는 부분

for (int i = 0; i < n; i++) {
    dp[n - 1][i] = triangle[n - 1][i];
}

---

📌 dp 배열 업데이트

• i는 현재 행을 나타내며, 아래에서 위로 순회
• j는 현재 열을 나타내며, 각 위치에서의 최대 합을 계산
• $Math.max$ 함수로 두 계산 중 하나를 선택하여 저장

for (int i = n - 2; i >= 0; i--) {
    for (int j = 0; j <= i; j++) {
        dp[i][j] = triangle[i][j] + Math.max(dp[i + 1][j], dp[i + 1][j + 1]);
    }
}

---

👀 예시 삼각형

    7
   3 8
  8 1 0
 2 7 4 4
4 5 2 6 5

1️⃣ DP 배열 초기화

    x
   x x
  x x x
 x x x x
4 5 2 6 5

2️⃣ DP 배열 업데이트

맨 아래에서 한줄씩 올라가며 최고값 계산

        x
      x   x
    x   x   x
  7  12  10  10
4   5   2   6   5

        x
      x   x
   20  13  10
  7  12  10  10
4   5   2   6   5

       x
     23  21
   20  13  10
  7  12  10  10
4   5   2   6   5

       30
     23  21
   20  13  10
  7  12  10  10
4   5   2   6   5

즉 정답은 30 이 된다

3️⃣ dp 배열은 최종적으로

{{30}, {23, 21}, {20, 13, 10}, {7, 12, 10, 10}, {4, 5, 2, 6, 5}}
이 되므로,
dp[0][0] 을 반환하면 된다는거!

---

💻 최종 코드 💻

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

        for (int i = 0; i < n; i++) {
            dp[n - 1][i] = triangle[n - 1][i];
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = triangle[i][j] + Math.max(dp[i + 1][j], dp[i + 1][j + 1]);
            }
        }
        return dp[0][0];
    }
    public static void main(String[] args) {
        int[][] triangle = {{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}};
        Solution sol = new Solution();
        System.out.println(sol.solution(triangle));
    }
}

👏👏👏👏👏👏👏👏👏