2324252627282930313233343536373839404142434445

class Solution:
    # Function to find the minimum path sum using tabulation
    def func(self, triangle, n, dp):
        """ Initialize the bottom row of dp
        with the values from the triangle"""
        for j in range(n):
            dp[n - 1][j] = triangle[n - 1][j]

        # Iterate through the triangle rows in reverse order
        for i in range(n - 2, -1, -1):
            for j in range(i + 1):
                # Calculate the minimum path sum for current cell
                down = triangle[i][j] + dp[i + 1][j]
                diagonal = triangle[i][j] + dp[i + 1][j + 1]

                # Store the minimum of the two possible paths in dp
                dp[i][j] = min(down, diagonal)

        # Top-left cell of dp now contains the minimum path sum
        return dp[0][0]

    # Function to find out the minimum path sum
    def minTriangleSum(self, triangle):
        # Get the number of rows in the triangle
        n = len(triangle)

        # Initialize a memoization table to store computed results
        dp = [[0] * n for _ in range(n)]

        # Return the minimum path sum
        return self.func(triangle, n, dp)

triangle = [
    [1],
    [2, 3],
    [3, 6, 7],
    [8, 9, 6, 10]
]

# Create an instance of Solution class
sol = Solution()

# Call the minTriangleSum function and print result
print(sol.minTriangleSum(triangle))

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051

class Solution {
    // Function to find the minimum path sum using tabulation
    func(triangle, n, dp) {
        /* Initialize the bottom row of dp
        with the values from the triangle*/
        for (let j = 0; j < n; j++) {
            dp[n - 1][j] = triangle[n - 1][j];
        }

        // Iterate through the triangle rows in reverse order
        for (let i = n - 2; i >= 0; i--) {
            for (let j = i; j >= 0; j--) {
                // Calculate the minimum path sum for current cell
                let down = triangle[i][j] + dp[i + 1][j];
                let diagonal = triangle[i][j] + dp[i + 1][j + 1];

                // Store the minimum of the two possible paths in dp
                dp[i][j] = Math.min(down, diagonal);
            }
        }
        // Top-left cell of dp now contains the minimum path sum
        return dp[0][0];
    }

    // Function to find out the minimum path sum
    minTriangleSum(triangle) {
        // Get the number of rows in the triangle
        let n = triangle.length;
        
        /* Initialize a memoization table
        to store computed results*/
        let dp = new Array(n).fill().map(() => new Array(n).fill(0));
    
        // Return the minimum path sum
        return this.func(triangle, n, dp);
    }
}

let triangle = [
    [1],
    [2, 3],
    [3, 6, 7],