Canon Firmware Update# PhotoGear - 摄影器材
a*e
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 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
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];
}
};
