Minimum Score Triangulation of Polygon LeetCode solution in C++

1
class Solution {
2
 public:
3
  int f(int i, int j, vector<int> &values, vector<vector<int>> &dp) {
4
    if (i == j || i + 1 == j) return 0;
5
    if (dp[i][j] != -1) return dp[i][j];
6
    int res = INT_MAX;
7
    for (int k = i + 1; k < j; k++) {
8
      int temp = values[i] * values[j] * values[k] + f(k, j, values, dp) + f(i, k, values, dp);
9
      res = min(res, temp);
10
    }
11
    return dp[i][j] = res;
12
  }
13

14
  int minScoreTriangulation(vector<int> &values) {
15
    int n = values.size();
16
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
17
    return f(0, n - 1, values, dp);
18
  }