a***e
发帖数: 413 | 1 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.
我刚开始看DP，大概有点idea，但怎么都做不对。有同学知道下面这个double loop 到
底怎么错了吗？有什么好的学习DP的方法分享吗？多谢！
class Solution {
public:
int minCut(string s) {
int n=s.size();
if (n<=1) return 0;
vector> b(n, vector(n,false));
int cut[n+1];
for (int i=0; i<=n; i++)
{
cut[i]=i-1;
}
for (int i=0; i
{
for (int j=i; j>=0; j--)
{
if (s[i]==s[j]&&(i-j<2||b[i+1][j-1]))
{
b[i][j]=true;
cut[i]=min(cut[i],cut[j+1]+1);
}
}
}
return cut[n];
}
}; | a*****a
发帖数: 46 | 2 改成这样就可以了
if (s[i]==s[j]&&(i-j<2||(b[i-1][j+1])))
{
b[i][j]=true;
cut[i+1]=min(cut[i+1],cut[j]+1);
}
is
【在 a***e 的大作中提到】
: 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.
: 我刚开始看DP，大概有点idea，但怎么都做不对。有同学知道下面这个double loop 到
: 底怎么错了吗？有什么好的学习DP的方法分享吗？多谢！
: class Solution {
: public:
| a***e
发帖数: 413 | 3 多谢大牛，这类题得多做才能积累经验是吗？总觉得状态转移方程很晕。 |
|
