120. Triangle

https://leetcode.com/problems/triangle/

Triangle - LeetCode

class Solution {
public:
    int minimumTotal(vector<vector<int>>& tri) {
        int n = tri.size();
        vector<int> mem(tri.back());
        
        for (int i = n - 2; 0 <= i; --i) {
            for (int j = 0; j <= i; ++j) {
                int v = tri[i][j];
                mem[j] = min(mem[j], mem[j + 1]) + v;
            }
        }
        
        return mem[0];
    }
};

Top-Down & Bottom-Up 방식을 비교해보자

[Top-Down]

• 직관적, 확장성
• 메모이제이션 공간이 2개 필요
• 코너 케이스 고려 
• 최종 결과를 별도로 계산

[Bottom-Up]

• 메모이제이션 공간이 1개 필요
• 코너 케이스 고려하지 않는다
• Root 값이 곧 최종 결과 값
• 폐쇄적