Question

How to get the minimum path sum from top to bottom in a triangle vector with C++

Answer 1

#include <iostream>
#include <vector>
#include <algorithm> // For std::min

int minimum_path_sum_recursion(int i, int j, int len, const std::vector<std::vector<int>>& triangle) {
    if (i == len) return 0;

    int lower_left = triangle[i][j] + minimum_path_sum_recursion(i + 1, j, len, triangle);
    int lower_right = triangle[i][j] + minimum_path_sum_recursion(i + 1, j + 1, len, triangle);
        
    return std::min(lower_left, lower_right);
}

int minimum_path_sum(const std::vector<std::vector<int>>& triangle) {
    return minimum_path_sum_recursion(0, 0, triangle.size(), triangle);
}

int main() {
    std::vector<std::vector<int>> triangle = {
         {2},
        {3, 4},
       {6, 5, 7},
     {4, 1, 8, 3}};
    
    // 2 + 3 + 5 + 1 = 11
    
    std::cout << "Minimum path sum: " << minimum_path_sum(triangle) << std::endl;
}

      
/*
run:
      
Minimum path sum: 11

*/

 

70+ SQL courses for beginners and professionals