leetcode

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

0132.cpp (592B)

      1 class Solution {
      2   public:
      3     int minCut(const string &s) const {
      4         static bool dp[2001][2001];
      5         static int cut[2001];
      6         const int n = s.size();
      7 
      8         memset(dp, 0x00, sizeof(dp));
      9         for (int i = 0; i < n; i++) {
     10             int mini = i;
     11             for (int j = 0; j <= i; j++) {
     12                 if (s[i] == s[j] && (i - j < 3 || dp[i - 1][j + 1])) {
     13                     mini = j == 0 ? 0 : min(mini, cut[j - 1] + 1);
     14                     dp[i][j] = true;
     15                 }
     16             }
     17             cut[i] = mini;
     18         }
     19 
     20         return cut[n - 1];
     21     }
     22 };