Leetcode 120 Solution

This article provides solution to leetcode question 120 (triangle)

https://leetcode.com/problems/triangle

Solution

class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { int n = triangle.size(); vector<vector<int>> dp;
if (n == 0) return 0;
for (int i = 0; i < n; i++) { vector<int> b(i + 1); dp.push_back(b); }
for (int i = n - 1; i >= 0; i--) { if (i == n - 1) { for (int j = 0; j < i + 1; j++) { dp[i][j] = triangle[i][j]; } } else { for (int j = 0; j < i + 1; j++) { dp[i][j] = triangle[i][j] + min(dp[i + 1][j], dp[i + 1][j + 1]); } } }
return dp[0][0]; } };