leetcode

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