Minimum Sum Path in a Triangle in C++

Problem statement

Given a triangular structure of numbers, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

Example

If input is −

   5   7 3  8 1 2 9 6 4 5

Then minimum sum is 13 as follows −

5 + 3 + 1 + 4

Algorithm

• Use memorization technique of dynamic programming
• Create 1-D array for memorization namely memorization
• For each K row use below formula −

memorization[i] = min( memorization[i], memorization[i+1]) + A[k][i];

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; int getMinSum(vector<vector<int>> &arr) {    int memorization[arr.size()];    int n = arr.size() - 1;    for (int i = 0; i < arr[n].size(); ++i) {       memorization[i] = arr[n][i];    }    for (int i = arr.size() - 2; i >= 0; --i) {       for (int j = 0; j < arr[i + 1].size() - 1; ++j) {          memorization[j] = arr[i][j] +          min(memorization[j],          memorization[j + 1]);       }    }    return memorization[0]; } int main() {    vector<vector<int>> arr = {    {5},    {7, 3},    {8, 1, 2},    {9, 6, 4, 5}, };    cout << "Minimum sum path = " << getMinSum(arr) << endl;    return 0; }

When you compile and execute above program. It generates following output −

Output

Minimum sum path = 13