120 Triangle

1. Dynamic Programing

int minimumTotal(vector<vector<int>> &triangle)
{
    for (int i = 1; i < triangle.size(); i++)
    {
        for (int j = 0; j <= i; j++)
        {
            triangle[i][j] += min(triangle[i - 1][max(0, j - 1)], triangle[i - 1][min(i - 1, j)]);
        }
    }
    int res = INT_MAX;
    for (int i = 0; i < triangle.size(); i++)
    {
        res = min(res, triangle.back()[i]);
    }
    return res;
}

Space	Time
$O(1)$	$O(n^2)$