C****y
发帖数: 77 | 1 Last executed input: "eegiicgaeadbcfacfhifdbiehbgejcaeggcgbahfcajfhjjdgj"
但是offline测试是通过了，研究了半天没找出来为何。
求大神指点。
Code:
class Solution {
public:
int minCut(string s) {
int len = s.length();
vector dp(len, len);
for (int i = 0; i < len; i++) {
dp[i] = i;
}
vector > pM(len, vector(len, false));
for (int l = 1; l < len + 1; l++) {
for (int i = 0; i < len; i++) {
int j = i + l -1;
pM[i][j] = (s[i] == s[j] && (j - i < 2 || pM[i+1][j-1]));
}
}
for (int i = 1; i < len; i++) {
for (int j = 0; j <= i; j++) {
if (pM[j][i]) {
if (j == 0) {
dp[i] = 0;
break;
}
if (dp[i] > dp[j-1] + 1) {
dp[i] = dp[j-1] + 1;
}
}
}
}
return dp[len-1];
}
}; |
|
