Triangle - 2D Dynamic Programming

My approach:

Even though it is not a complete N*N 2d array, the concept remains the same. We figure out the test cases and return the minimum after recurrence relation.

In this, we have a fixed starting point and a variable ending point. So we will have to do extra work to find the right answer because every time it reaches the last row it is a potential answer.

My solution:

• Recursive

• Iterative

Code:

• Memoization

#include <bits/stdc++.h> 

int helper(vector<vector<int>>& triangle, int n, int i, int j, vector<vector<int>> &dp){
    if(i>=n || j>i){
        return -1e8;
    }

    if(i==n-1){
        return triangle[i][j];
    }

    if(dp[i][j]!=-1){
        return dp[i][j];
    }

    int down = helper(triangle,n,i+1,j,dp);
    int diagonal = helper(triangle,n,i+1,j+1,dp);

    dp[i][j] = min(down,diagonal)+triangle[i][j];
    return min(down,diagonal)+triangle[i][j];
}

int minimumPathSum(vector<vector<int>>& triangle, int n){
    // Write your code here.
    vector<vector<int>> dp(n, vector<int>(n, -1));

    return helper(triangle,n,0,0,dp);
}

• Tabulation

#include <bits/stdc++.h> 

int minimumPathSum(vector<vector<int>>& triangle, int n){
    // Write your code here.
    vector<vector<int>> dp(n, vector<int>(n));

    dp[0][0] = triangle[0][0];

    //   Filling the 0th column
    for(int i=1;i<n;i++){
        dp[i][0] = dp[i-1][0]+triangle[i][0];
    }

    //   filing the last element of each row
    for(int i=1;i<n;i++){
        dp[i][i] = dp[i-1][i-1]+triangle[i][i];
    }

    for(int i=2;i<n;i++){
        for(int j=1;j<i;j++){
            int up = has
            int diagonal = dp[i-1][j-1]+triangle[i][j];

            dp[i][j] = min(up, diagonal);
        }
    }

    int minSum = INT_MAX;
    for(int i=0;i<n;i++){
        minSum = min(minSum, dp[n-1][i]);
    }

    return minSum;

}

Question Link:

https://www.codingninjas.com/studio/problems/triangle_1229398?leftPanelTab=0