题解 | #分割回文串-ii#

这里用了dp数组记录最小值,第一位dp[0]=-1,目的很简单,当j=0,整体是回文串时, 代码可以复用,-1+1=0; 也可以用递归的方法

public:
	/**
	 *
	 * @param s string字符串
	 * @return int整型
	 */

	bool isPalindrome(string& s, int j, int i)
	{
		string str = s.substr(j, i - j + 1);
		int len = str.length();
		for (int i = 0, j = len - 1; i < j; ++i, --j)
		{
			if (str[i] != str[j])
				return false;
		}
		return true;
	}

	int minCut(string s) {
		// write code here
		int lens = s.length();
		vector<int> dp(lens + 1);
		for (int i = 0; i <= lens; ++i)dp[i] = i - 1;
		for (int i = 1; i <= lens; ++i)
		{
			for (int j = 0; j < i; ++j)
			{
				if (isPalindrome(s, j, i-1))
					dp[i] = min(dp[i], dp[j] + 1);
			}
		}
		return dp[lens];
	}
};