leetcode

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];