leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1039.cpp (811B)

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