2014
11-18

# LeetCode-Palindrome Partitioning II[动态规划]

### Palindrome Partitioning II

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.

$$f(i,j)=\min\left\{f(i,k)+f(k+1,j)\right\}, i \leq k \leq j, 0 \leq i \leq j<n$$

$$f(i)=\min\left\{f(j+1)+1\right\}, i \leq j<n$$

\begin{Code}
P[i][j] = str[i] == str[j] && P[i+1][j-1]
\end{Code}

// LeetCode, Palindrome Partitioning II
// 时间复杂度O(n^2)，空间复杂度O(n^2)
class Solution {
public:
int minCut(string s) {
const int n = s.size();
int f[n+1];
bool p[n][n];
fill_n(&p[0][0], n * n, false);
//the worst case is cutting by each char
for (int i = 0; i <= n; i++)
f[i] = n - 1 - i; // 最后一个f[n]=-1
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (s[i] == s[j] && (j - i < 2 || p[i + 1][j - 1])) {
p[i][j] = true;
f[i] = min(f[i], f[j + 1] + 1);
}
}
}
return f[0];
}
};


Java代码:

public class Solution {
public int minCut(String s) {
int n = s.length();
boolean isPal[][] = new boolean[n][n];
int dpminc[] = new int[n];
for (int j = 0; j < n; j++){
dpminc[j] = j;
for (int i = 0; i <= j; i++){
if(s.charAt(i) == s.charAt(j) && (j - i <= 1 || isPal[i+1][j-1]) ){
isPal[i][j] = true;
if(i > 0)
dpminc[j] = Math.min(dpminc[j], dpminc[i - 1] + 1);
else
dpminc[j] = 0;
}
}
}
return dpminc[n-1];
}
}

1. 我感觉之后卡卡西会当火影 因为鸣人 和佐助实力相当 他们嘴上说当火影 其实心里还是会有所谦让 然后带土会把另一只眼睛给卡卡西 这是大量粉丝猜测

2. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}

3. 嗯 分析得很到位，确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样：push时，比较要push的elem和辅助栈的栈顶，elem<=min.top()，则min.push(elem).否则只要push（elem）就好。在pop的时候，比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();}，否则{stack.pop();}.