Notes:

1. If len < 2, return 0. It is not minimum length but how many cuts.

2. As it was cutting inside of string. Final result is dp[0] - 1, since there is no cut at most left.

1 class Solution { 2 public: 3     int minCut(string s) { 4         int len = s.size(); 5         if (len < 2) return 0; 6         vector
     
       dp(len+1, 0); 7         vector
      
       
         > rec(len, vector
        
         (len, false)); 8         for (int i = 0; i <= len; i++) dp[i] = len - i; 9         for (int i = len-1; i >= 0; i--) {10             for (int j = i; j < len; j++) {11                 if (s[i] == s[j] && (j - i < 2 || rec[i+1][j-1])) {12                     rec[i][j] = true;13                     dp[i] = min(dp[i], dp[j+1]+1);14                 }15             }16         }17         return dp[0]-1;18     }19 };