Triangle

class Solution {
private:
    vector<vector<int>> grid;
    map<pair<int, int>, int> cache;
    int findMinPath(int i, int j) {
        if (cache.find({i, j}) != cache.end()) {
            return cache[{i, j}];
        }
        int currentSum = grid[i][j];
        if (i < grid.size() - 1) {
            currentSum += min(findMinPath(i + 1, j), findMinPath(i + 1, j + 1));
        }
        cache[{i, j}] = currentSum;
        return currentSum;
    }
    
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        this->grid = triangle;
        return findMinPath(0, 0);
    }
};

The provided C++ code addresses the problem of finding the minimum path sum from the top of the triangle to the bottom. The "Triangle" input is represented as a 2D vector wherein each element corresponds to a point in the triangle containing an integer weight.

Key components of the solution:

• Data Structures:

  • Uses a vector<vector<int>> to store the triangle grid.
  • Employs a map<pair<int, int>, int> to cache computed results for specific coordinates (i, j) enhancing efficiency by avoiding repeated calculations.

• Private Method findMinPath:

  • It recursively calculates the minimal path sum starting from the top of the triangle.
  • Implements memoization by storing results in the cache. If a result for a specific node (i, j) is already computed, it is retrieved from the cache, thus saving computation time.
  • The method adds node's value to the minimum of the sums from the two possible paths downward (directly below left, directly below right).

• Public Method minimumTotal:

  • It initializes the internal grid with the triangle data passed as an argument.
  • Returns the result of findMinPath method initiated from the top of the triangle, which is the start point (0,0).

By using dynamic programming principles, specifically memoization, the solution efficiently finds the minimal path sum, ensuring that the algorithm will perform well even for larger triangles.

class Solution {
    private Map<String, Integer> memoizationCache;
    private List<List<Integer>> pyramid;
    
    private int findMinPath(int level, int index) {
        String key = level + "," + index;
        if (memoizationCache.containsKey(key)) {
            return memoizationCache.get(key);
        }
        int minValue = pyramid.get(level).get(index);
        if (level < pyramid.size() - 1) {
            minValue += Math.min(findMinPath(level + 1, index), findMinPath(level + 1, index + 1));
        }
        memoizationCache.put(key, minValue);
        return minValue;
    }
    
    public int minimumTotal(List<List<Integer>> triangle) {
        this.pyramid = triangle;
        memoizationCache = new HashMap<>();
        return findMinPath(0, 0);
    }
}

The solution provided is for finding the minimum path sum from the top to the bottom of a triangle array using Java. The approach involves dynamic programming with memoization to optimize repeated calculations.

The code defines a Solution class with:

• A private Map<String, Integer> to serve as a memoization cache.
• A private List<List<Integer>> which holds the triangle data.

Key functions include:

• findMinPath(int level, int index): This recursive helper function computes the minimum path sum starting from a given level and index in the triangle. It uses a key generated from the current level and index to check if the result is already in the memoizationCache. If not, it computes the minimum path sum for the current node and stores it in the cache.
• minimumTotal(List<List<Integer>> triangle): This is the public method that initializes the pyramid with the triangle data and the memoizationCache with a new HashMap. It starts the path calculation by calling findMinPath(0, 0).

This implementation effectively reduces the complexity of the problem by avoiding recomputation of the same paths, leveraging the memoization technique. The use of recursion and cache effectively decomposes the problem into simpler, manageable subproblems, resulting in a more efficient solution.

struct position {
    int x;
    int y;
};
struct cache_table {
    struct position pos;
    int value;
    UT_hash_handle hh;
};
struct cache_table* cachingTable = NULL;
void insert(struct position pos, int value) {
    struct cache_table* entry;
    HASH_FIND(hh, cachingTable, &pos, sizeof(struct position), entry);
    if (entry == NULL) {
        entry = (struct cache_table*)malloc(sizeof *entry);
        entry->pos = pos;
        entry->value = value;
        HASH_ADD(hh, cachingTable, pos, sizeof(struct position), entry);
    } else {
        entry->value = value;
    }
}
int lookup(struct position pos) {
    struct cache_table* entry;
    HASH_FIND(hh, cachingTable, &pos, sizeof(struct position), entry);
    if (entry == NULL) return -1;
    return entry->value;
}
int** triangleGrid;
int rowCount;
int* columnSizes;
int findMinPath(int x, int y) {
    struct position pos;
    pos.x = x;
    pos.y = y;
    int cachedVal = lookup(pos);
    if (cachedVal != -1) {
        return cachedVal;
    }
    int result = triangleGrid[x][y];
    if (x < rowCount - 1) {
        result += fmin(findMinPath(x + 1, y), findMinPath(x + 1, y + 1));
    }
    insert(pos, result);
    return result;
}
int minimumTriangleTotal(int** triangle, int numRow, int* colSizes) {
    triangleGrid = triangle;
    rowCount = numRow;
    columnSizes = colSizes;
    cachingTable = NULL;  // clear cache table before starting
    return findMinPath(0, 0);
}

The provided C code defines a solution to determine the minimum total from top to bottom in a triangle made up of integers. The code uses dynamic programming combined with memoization to optimize computations. Below is a summary of how the code functions:

1. Structures define:

   • struct position to hold x and y coordinates within the triangle.
   • struct cache_table to create a hashtable cache for storing computed results at specific positions to prevent redundant calculations.

2. Helper functions for cache operations:

   • insert adds a new result to the cache or updates an existing entry.
   • lookup retrieves a cached result if it exists.

3. Central processing functions:

   • findMinPath calculates the minimum path sum to a particular position (x, y) in the triangle using recursion. It uses memoization to store previously computed results and avoid repeated calculations for the same positions.
   • minimumTriangleTotal initializes the necessary variables, clears the cache, and starts the calculation by calling findMinPath.

The code employs the UTHash library for efficient hashing operations which is used to handle the caching mechanism. This solution is efficient for processing larger triangles because it ensures that each sub-problem is solved only once, thus reducing the overall computational complexity. The memoization technique is especially useful in this scenario, as it significantly cuts down the number of redundant operations by retrieving stored results from a hash table.

let pyramid;
let cache = new Map();
function shortestPath(i, j) {
    let key = i + ':' + j;
    if (cache.has(key)) {
        return cache.get(key);
    }
    let route = pyramid[i][j];
    if (i < pyramid.length - 1) {
        route += Math.min(shortestPath(i + 1, j), shortestPath(i + 1, j + 1));
    }
    cache.set(key, route);
    return route;
}
var minimumTotal = function (inputPyramid) {
    pyramid = inputPyramid;
    cache.clear();
    return shortestPath(0, 0);
};

This solution uses JavaScript to solve a problem involving finding the shortest path through a triangle (or pyramid-like structure) of numbers, where each step you may move to adjacent numbers on the row below. Here is the breakdown of the code implementation:

• Initialize pyramid to hold the triangle of numbers and cache using a JavaScript Map to memoize results and optimize performance by avoiding redundant calculations.
• Define shortestPath(i, j), a recursive function that:
  • Checks if the result for the current position (i, j) is already computed and stored in cache.
  • Calculates the sum of the current number pyramid[i][j] and the minimum of the paths from the two possible next positions (i+1, j) and (i+1, j+1).
  • Stores the computed value in cache to reuse for later overlapping subproblems.
• Create minimumTotal(inputPyramid), which:
  • Sets the global pyramid variable to the input triangle.
  • Clears the cache for fresh computation.
  • Returns the result of the shortestPath function starting from the top of the triangle (0,0).

The approach effectively incorporates dynamic programming through memoization to ensure that the solution is efficient, particularly for large triangles, by reducing the time complexity that would otherwise be exponential due to repeated computations in a plain recursive approach.

class Solution:
    def minimumTriangleSum(self, triangle: List[List[int]]) -> int:
        @lru_cache(maxsize=None)
        def path_sum(r, c):
            sum_val = triangle[r][c]
            if r < len(triangle) - 1:
                sum_val += min(path_sum(r + 1, c), path_sum(r + 1, c + 1))
            return sum_val
    
        return path_sum(0, 0)

This solution addresses the problem of finding the minimum triangle sum in a triangular array. The provided code is implemented in Python and uses a class-based approach with recursion and memoization to optimize performance.

• The Solution class contains a method minimumTriangleSum, which calculates the minimum path sum from the top to the bottom of the triangle.
• The path_sum helper function is a nested function inside minimumTriangleSum and uses r and c to denote the current row and column indices in the triangle.
• The lru_cache decorator from the functools module is applied to path_sum to memoize the results of recursive calls, reducing the number of redundant calculations and thus enhancing the efficiency.
• The recursion base condition is set for when the function reaches the last row of the triangle, and it simply returns the value at the current position.
• For other cases, path_sum adds the current triangle number to the minimum of the sums derived from the two possible paths in the row immediately below (directly downward or diagonally right downward).
• The final result is obtained by calling path_sum(0, 0), initiating the recursive calculation from the top of the triangle.

This solution efficiently computes the minimum path sum using dynamic programming techniques with a recursive function and caching. Optimal substructure and overlapping sub-problems properties are harnessed, which are typical in dynamic programming solutions to such problems.