leetcode

Solution to some Leetcode problems written in C++

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

1547.cpp (566B)

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