Leet Palindrome Partitioning II

 1 class Solution {

 2 public:

 3     int minCut(string s) {

 4         int len = s.length();

 5         int*  p_dp = new int[len + 1];

 6         char* s_dp = new char[len * len];

 7         int*  mm = new int[len + 1];

 8         mm[0] = 0;

 9         memset(s_dp, -1, len * len);

10         memset(p_dp, 0, (len + 1) * sizeof(int));

11 

12         int ret;

13         for (int i=1; i<=len; i++) {

14             int sub_len = i;

15             int minc = INT_MAX;

16 

17             for (int j=0; j<=i-1; j++, sub_len--) {

18 

19                 char* p_is = &s_dp[j * len + i-1];

20                 char b = 0;

21                 if (sub_len >= 3 && -1 != (b = s_dp[(j+1) * len + i - 2])) {

22                     *p_is = b && (s[j] == s[j + sub_len - 1]);

23                 }

24                 if (*p_is == -1) {

25                     int p = j, q = j + sub_len - 1;

26                     for (; p < q && s[p] == s[q]; p++, q--);

27                     *p_is = (p < q) ? 0 : 1;

28                 }

29                 if (*p_is == 0) continue;

30                 if (p_dp[j] < minc) minc = p_dp[j];

31                 if (minc == mm[j]) break;

32             }

33             p_dp [i] = minc + 1;

34             mm[i] = p_dp[i];

35             for (int k = i-1; k >=0 && mm[k]>mm[k+1]; k--) {

36                 mm[k] = mm[k+1];

37             }

38         }

39         ret = p_dp[len];

40         delete[] mm;

41         delete[] p_dp;

42         delete[] s_dp;

43         return ret - 1;

44     }

45 };

前の問題でdpのような方法が考えられた以上、この問題はもっと簡単だと思っていたが...でも...判断文の着过プロセスを最适化していないで、ずっとTLE、それを考虑して过ごすことができて、ここで文字列が回文の过程を求めるかどうかと最小の分割を求める过程を合并して、しかももっと小さい分割があり得ない情况の下で急速に次の循环の过程に入ることを考えて、悲剧の一日.