leetcode

0 class Solution {

1 int dp[102][102] = {};

2

3 int dfs(const vector<int> &cuts, int i, int j) {

4 if (j - i <= 1) return 0;

5 if (dp[i][j]) return dp[i][j];

6 dp[i][j] = INT_MAX;

7 for (auto k = i + 1; k < j; ++k)

8 dp[i][j] = min(dp[i][j], cuts[j] - cuts[i] + dfs(cuts, i, k) + dfs(cuts, k, j));

9 return dp[i][j];

10 }

11

12 public:

13 int minCost(int n, vector<int> &cuts) {

14 cuts.push_back(0);

15 cuts.push_back(n);

16 sort(begin(cuts), end(cuts));

17 return dfs(cuts, 0, cuts.size() - 1);

18 }

19 };