Minimum Cost Tree From Leaf Values Solutions in C++

/// Source : https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/
/// Author : liuyubobobo
/// Time   : 2019-07-20

#include <iostream>
#include <vector>

using namespace std;


/// Memory Search
/// Time Complexity: O(n^3)
/// Space Complexity: O(n^2)
class Solution {

private:
    int n;

public:
    int mctFromLeafValues(vector<int>& arr) {

        n = arr.size();
        vector<vector<int>> maxv(n,vector<int>(n));
        for(int i = 0; i < n; i ++) maxv[i][i] = arr[i];
        for(int d = 1; d < n; d ++)
            for(int i = 0; i + d < n; i ++)
                maxv[i][i + d] = max(maxv[i][i + d - 1], maxv[i + 1][i + d]);

        vector<vector<int>> dp(n, vector<int>(n, -1));
        return search(arr, 0, n - 1, maxv, dp);
    }

    int search(const vector<int>& arr, int l, int r,
               vector<vector<int>>& maxv, vector<vector<int>>& dp){

        if(l == r)
            return 0;

        if(dp[l][r] != -1) return dp[l][r];

        int res = INT_MAX;
        for(int mid = l; mid < r; mid ++){
            int lres = search(arr, l, mid, maxv, dp);
            int rres = search(arr, mid + 1, r, maxv, dp);
            res = min(res, lres + rres + maxv[l][mid] * maxv[mid + 1][r]);
        }

        return dp[l][r] = res;
    }
};


int main() {

    vector<int> vec = {6, 2, 4};
    cout << Solution().mctFromLeafValues(vec) << endl;
    // 32

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/
/// Author : liuyubobobo
/// Time   : 2019-08-22

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(n^3)
/// Space Complexity: O(n^2)
class Solution {

public:
    int mctFromLeafValues(vector<int>& arr) {

        int n = arr.size();
        vector<vector<int>> maxv(n,vector<int>(n));
        for(int i = 0; i < n; i ++) maxv[i][i] = arr[i];
        for(int d = 1; d < n; d ++)
            for(int i = 0; i + d < n; i ++)
                maxv[i][i + d] = max(maxv[i][i + d - 1], maxv[i + 1][i + d]);

        vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
        for(int i = 0; i < n; i ++) dp[i][i] = 0;
        for(int d = 1; d < n; d ++)
            for(int i = 0; i + d < n; i ++)
                for(int mid = i; mid < i + d; mid ++)
                    dp[i][i + d] = min(dp[i][i + d], dp[i][mid] + dp[mid + 1][i + d] + maxv[i][mid] * maxv[mid + 1][i + d]);
        return dp[0][n - 1];
    }
};


int main() {

    vector<int> vec1 = {6, 2, 4};
    cout << Solution().mctFromLeafValues(vec1) << endl;
    // 32

    vector<int> vec2 = {7, 12, 8, 10};
    cout << Solution().mctFromLeafValues(vec2) << endl;
    // 284

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/
/// Author : liuyubobobo
/// Time   : 2019-08-22

#include <iostream>
#include <vector>
#include <stack>

using namespace std;


/// Greedy
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

public:
    int mctFromLeafValues(vector<int>& arr) {

        int n = arr.size();
        if(n == 1) return 0;

        stack<int> stack;
        stack.push(0);
        int res = 0;
        for(int i = 1; i < n; i ++){
            while(!stack.empty() && arr[stack.top()] < arr[i]){
                int cur = stack.top();
                stack.pop();
                if(stack.empty())
                    res += arr[cur] * arr[i];
                else
                    res += arr[cur] * min(arr[stack.top()], arr[i]);
            }
            stack.push(i);
        }

        while(stack.size() >= 2){
            int x = arr[stack.top()];
            stack.pop();
            res += x * arr[stack.top()];
        }
        return res;
    }
};


int main() {

    vector<int> vec1 = {6, 2, 4};
    cout << Solution().mctFromLeafValues(vec1) << endl;
    // 32

    vector<int> vec2 = {7, 12, 8, 10};
    cout << Solution().mctFromLeafValues(vec2) << endl;
    // 284

    vector<int> vec3 = {6, 15, 5, 2};
    cout << Solution().mctFromLeafValues(vec3) << endl;
    // 175

    vector<int> vec4 = {15, 13, 5, 3, 15};
    cout << Solution().mctFromLeafValues(vec4) << endl;
    // 500

    vector<int> vec5 = {6, 9, 6, 15, 15};
    cout << Solution().mctFromLeafValues(vec5) << endl;
    // 468

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/
/// Author : liuyubobobo
/// Time   : 2019-08-22

#include <iostream>
#include <vector>
#include <stack>

using namespace std;


/// Greedy
/// Using sentel to make the logic more concise
///
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

public:
    int mctFromLeafValues(vector<int>& arr) {

        arr.insert(arr.begin(), INT_MAX);
        arr.push_back(INT_MAX);

        stack<int> stack;
        int res = 0;
        for(int i = 0; i < arr.size(); i ++){
            while(!stack.empty() && arr[stack.top()] < arr[i]){
                int cur = stack.top();
                stack.pop();
                int minv = min(arr[stack.top()], arr[i]);
                if(minv != INT_MAX) res += arr[cur] * minv;
            }
            stack.push(i);
        }
        return res;
    }
};


int main() {

    vector<int> vec1 = {6, 2, 4};
    cout << Solution().mctFromLeafValues(vec1) << endl;
    // 32

    vector<int> vec2 = {7, 12, 8, 10};
    cout << Solution().mctFromLeafValues(vec2) << endl;
    // 284

    vector<int> vec3 = {6, 15, 5, 2};
    cout << Solution().mctFromLeafValues(vec3) << endl;
    // 175

    vector<int> vec4 = {15, 13, 5, 3, 15};
    cout << Solution().mctFromLeafValues(vec4) << endl;
    // 500

    vector<int> vec5 = {6, 9, 6, 15, 15};
    cout << Solution().mctFromLeafValues(vec5) << endl;
    // 468

    return 0;
}