Palindrome Partitioning II -interesting

 //there is a related problem: longest palindrome substring
Note that in the following solution, to accommodate the dp computation of palin, we define dp[i] to be the mincut for the substring from i to the end.
     int minCut(string str) {
        int leng = str.size();

        int dp[leng+1];
        bool palin[leng][leng];

      for(int i = 0; i <= leng; i++)
        dp[i] = leng-i-1;
      for(int i = 0; i < leng; i++)
          for(int j = 0; j < leng; j++)
                palin[i][j] = false;

      for(int i = leng-1; i >= 0; i--){
        for(int j = i; j < leng; j++){
          if(str[i] == str[j] && (j-i<2 || palin[i+1][j-1])){
            palin[i][j] = true;
            dp[i] = min(dp[i],dp[j+1]+1);
          }
        }
      }
      return dp[0];
    }

 //one dimension dp, by anniekim
   int minCut(string s) {
        int N = s.size();
        bool isP[N];
        int dp[N];
        dp[0] = 0;
        for (int i = 1; i < N; ++i)
        {
            isP[i] = true;
            dp[i] = dp[i-1] + 1;
            for (int j = 0; j < i; ++j)
            {
                isP[j] = (s[i] == s[j]) ? isP[j+1] : false; // isP[j] == true -> [j...i] is a palindrome
                                                            // isP[j+1] == true -> [j+1...i-1] is a palindrome
                if (isP[j])
                    dp[i] = (j == 0) ? 0 : min(dp[i], dp[j-1] + 1); // dp[i] -> minCount for [0...i]
            }
        }
        return dp[N-1];
    }