leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1039.cpp (811B)

      1 class Solution {
      2     static int dp[51][51];
      3 
      4     static int solve(const int *data, int low, int high) {
      5         if (high - low < 2) return 0;
      6         if (dp[low][high] != -1) return dp[low][high];
      7         int res = INT_MAX;
      8         if (high - low == 2)
      9             res = data[low] * data[low + 1] * data[low + 2];
     10         else {
     11             const int base = data[low] * data[high];
     12             for (int i = low + 1; i < high; i++) {
     13                 res = min(res, base * data[i] + solve(data, low, i) + solve(data, i, high));
     14             }
     15         }
     16         return dp[low][high] = res;
     17     }
     18 
     19   public:
     20     Solution() { memset(dp, 0xFF, sizeof(dp)); }
     21     int minScoreTriangulation(const vector<int> &values) const {
     22         return solve(values.data(), 0, size(values) - 1);
     23     }
     24 };
     25 
     26 int Solution::dp[51][51];