leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1547.cpp (566B)

      1 class Solution {
      2     int dp[102][102] = {};
      3 
      4     int dfs(const vector<int> &cuts, int i, int j) {
      5         if (j - i <= 1) return 0;
      6         if (dp[i][j]) return dp[i][j];
      7         dp[i][j] = INT_MAX;
      8         for (auto k = i + 1; k < j; ++k)
      9             dp[i][j] = min(dp[i][j], cuts[j] - cuts[i] + dfs(cuts, i, k) + dfs(cuts, k, j));
     10         return dp[i][j];
     11     }
     12 
     13   public:
     14     int minCost(int n, vector<int> &cuts) {
     15         cuts.push_back(0);
     16         cuts.push_back(n);
     17         sort(begin(cuts), end(cuts));
     18         return dfs(cuts, 0, cuts.size() - 1);
     19     }
     20 };