Triangle 🌟🌟

Recursive Solution

• As triangle[0][0] is stable, we can start from there instead of starting from the bottom.
• For every element, we can either go to the element below it or the element below and to the right of it adding the value of the current element to the sum.
• We choose to go with minimum of the two.
• when we reach to the last row, we return the value of the element.
• TC: O(2^n)
• SC: O(n)

Code

int f(vector<vector<int>>& triangle, int n, int i, int j)
{
    if (i == n - 1)
        return triangle[i][j];
    int down = triangle[i][j] + f(triangle, n, i + 1, j);
    int dig = triangle[i][j] + f(triangle, n, i + 1, j + 1);
    return min(down, dig);
}

int minimumPathSum(vector<vector<int>>& triangle, int n)
{
    return f(triangle, n, 0, 0);
}

Memoization(top-down)

• The recursive solution obviously gives TLE, so we can reduce the time complexity by using memoization.
• TC: O(n^2)
• SC: O(n^2), with recursion stack space of O(n)

Code

int f(vector<vector<int>>& triangle, int n, int i, int j, vector<vector<int>>& dp)
{
    if (i == n - 1)
        return triangle[i][j];
    if (dp[i][j] != -1)
        return dp[i][j];
    int down = triangle[i][j] + f(triangle, n, i + 1, j, dp);
    int dig = triangle[i][j] + f(triangle, n, i + 1, j + 1, dp);
    return dp[i][j] = min(down, dig);
}

int minimumPathSum(vector<vector<int>>& triangle, int n)
{
    vector<vector<int>> dp(n, vector<int>(n, -1));
    return f(triangle, n, 0, 0, dp);
}

Tabulation(bottom-up)

• To reduce recursive stack space we can do iterative dp.
• As we can see from the base case of memoization, we need to set last row of dp equal to last row of triangle.
• Now for i we were going from 0 to n-2 in memoization, but here we will go from n-2 to 0.
• For j we can go from 0 to n.
• In memoization we were calling the function for f(0,0) so here we return dp[0][0].
• TC: O(n^2)
• SC: O(n^2), without recursive stack space.

Code

int minimumPathSum(vector<vector<int>>& triangle, int n)
{
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int j = 0; j < n; j++) {
        dp[n - 1][j] = triangle[n - 1][j];
    }
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            int down = triangle[i][j] + dp[i + 1][j];
            int dig = triangle[i][j] + dp[i + 1][j + 1];
            dp[i][j] = min(down, dig);
        }
    }
    return dp[0][0];
}

Space Optimized Tabulation

• As for calculation we just require previous row and current row, we can reduce the space complexity.

• dp[i+1] = prev, as we are going from bottom to top
  dp[i] = curr
  

• TC: O(n^2)
• SC: O(n)

Code

int minimumPathSum(vector<vector<int>>& triangle, int n)
{
    vector<int> prev(n, 0), curr(n, 0);
    for (int j = 0; j < n; j++) {
        prev[j] = triangle[n - 1][j];
    }
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            int down = triangle[i][j] + prev[j];
            int dig = triangle[i][j] + prev[j + 1];
            curr[j] = min(down, dig);
        }
        prev = curr;
    }
    return prev[0];
}