leetcode

Solution to some Leetcode problems written in C++

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

0132.cpp (592B)

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