Palindrome Partitioning II

Palindrome Partitioning II

 Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

------------------------------- thinking -----------------------------------
https://oj.leetcode.com/discuss/19615/dp-solution-%26-some-thoughts
One thing I need to remember is how to correctly use memset()!!!!!!!
https://oj.leetcode.com/discuss/5586/memset-and-fill_n

very nice solution without using marker!!
https://oj.leetcode.com/discuss/9476/solution-does-not-need-table-palindrome-right-uses-only-space
-------------------------------- codes -------------------------------------
   class Solution {
   public:
       int minCut(string s) {
           int len = s.size();
           if (len <= 1) {
               return 0;
           }
           bool mark[len][len];
           memset(mark, false, sizeof(mark));
           for (int i = 0; i < len; i++) {
               mark[i][i] = true;
           }
           int dp[len+1];
           dp[0] = -1;
           for (int i = 1; i <= len; i++) {
               //bug here -> min should be i-1
               int min = i-1;
               for (int j = i-1; j >= 0; j--) {
                   if (s[i-1] == s[j] && (j+1 == i-1 || j == i-1 || mark[j+1][i-2])) {
                       mark[j][i-1] = true;
                       if (dp[j] + 1 < min) {
                           min = dp[j] + 1;
                       }
                   }
                   //else {
                   //    mark[j][i-1] = false;
                   //}
               }
               dp[i] = min;
           }
           return dp[len];
       }
   };
------------------------- codes / no mark is needed ----------------------------------
class Solution {
public:
    /**
     * @param s a string
     * @return an integer
     */
    int minCut(string s) {
        // write your code here
        vector<int> cur(s.size()+1);
        for (int i = 0; i <= s.size(); i++) {
            cur[i] = i-1;
        }
        for (int k = 1; k < s.size(); k++) {
            //odd counting
            //bug here, start and end should be set to k instead of k-1 and k+1
            int start = k;
            int end = k;
            while (start >= 0 && end < s.size() && s[start] == s[end]) {
                if (cur[end+1] > cur[start] + 1) {
                    cur[end+1] = cur[start] + 1;
                }
                start--;
                end++;
            }
            start = k - 1;
            end = k;
            while (start >= 0 && end < s.size() && s[start] == s[end]) {
                if (cur[end+1] > cur[start] + 1) {
                    cur[end+1] = cur[start] + 1;
                }
                start--;
                end++;
            }
        }
        return cur[s.size()];
    }
};