to do
- backtracking
- overview:
(so if we've tried all children of s.top(), it's now useless and to be thrown away. That's why if stack is ever empty, we know there's no solution) - If using stack(or recursion stack), at anytime the stack contains a reversed path from rootnode to current node.
- keep the methods simple, use helper such as
isLeaf()to hide details - keep track of which childs tried, by keeping an untried list or specify an order to try
- https://www.cis.upenn.edu/~matuszek/cit594-2012/Pages/backtracking.html
10.1] Palindrome partitioning
bool isPalindrome(string s) {
for (int l=0, r=s.size()-1; l<r; ++l, --r) {
if (s[l]!=s[r]) return false;
}
return true;
}
void dfs(vector<vector<string>>& ret, vector<string>& path, string s, int start) {
if (start==s.size()) {
ret.push_back(path);
return;
}
for (int i=start; i<s.size(); ++i) {
if (isPalindrome(s.substr(start, i-start+1))) {
path.push_back(s.substr(start, i-start+1));
dfs(ret, path, s, i+1);
path.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
if (s.empty()) return vector<vector<string>> {};
vector<vector<string>> ret;
vector<string> path;
dfs(ret, path, s, 0);
return ret;
}
- dp Palindrome Partitioning
In the first dp: pre-calculate isPalindrome, need to usep[i+1][j-1] at each step => decides the direction of two for loops in dp.
vector<vector<string>> partition(string s) {
if (s.empty()) return vector<vector<string>> {};
int n = s.size();
// dp: pre-calculate isPalindrome
bool p[n][n];
// fill_n(&p[0][0], n * n, false);
for (int i=n-1; i>=0; --i) {
for (int j=i; j<n; ++j) {
p[i][j] = s[i]==s[j] && ( j-i<2 || p[i+1][j-1] );
}
}
// dp: dfs
vector<vector<string>> dfs [n];
for (int i=n-1; i>=0; --i) {
vector<vector<string>>& path = dfs[i];
for (int j=i; j<n; ++j) {
if (p[i][j]) {
string strl = s.substr(i, j-i+1);
if (j+1==n) path.push_back(vector<string> {strl});
else {
for (vector<string> v: dfs[j+1]) {
v.insert(v.begin(), strl);
path.push_back(v);
}
}
}
} // end for j
}
return dfs[0];
}
2】 Palindrome Partitioning II
int minCut(string s) {
if (s.empty()) return 0;
int n = s.size();
// dp: pre-calculate isPalindrome
bool p[n][n];
for (int i=n-1; i>=0; --i) {
for (int j=i; j<n; ++j) {
p[i][j] = s[i]==s[j] && (j-i<2 || p[i+1][j-1]);
}
}
int minCut[n] = {0};
for (int i=1; i<n; ++i) {
minCut[i] = minCut[i-1]+1;
for (int j=i; j>=0; --j) { //cut at j-> [0..j..i]
if (p[j][i]) {
minCut[i] = j==0? 0: min(minCut[i], 1+minCut[j-1]);
}
}
}
return minCut[n-1];
}
- no palindrome memorization dp
機(jī)智的辦法留储，再揣摩
Its invariant is cuts[i-1] always hold the correct min Cut number.
int minCut(string s) {
int n = s.size();
int cuts[n+1];
for (int i=0; i<n+1; ++i) cuts[i] = i-1;
for (int i=0; i<n+1; ++i) {
// odd length palindrom
for (int j=0; j<=i && j+i<n && s[i-j]==s[i+j]; ++j) {
cuts[i+j+1] = min(cuts[i+j+1], 1+cuts[i-j]);
}
//even length
for (int j=1; j-1<=i && j+i<n && s[i-j+1]==s[i+j]; ++j) {
cuts[i+j+1] = min(cuts[i+j+1], 1+cuts[i-j+1]);
}
}
return cuts[n];
}
10.2] Unique Paths
int uniquePaths(int m, int n) {
if (!m || !n) return 0;
int path[m][n]; // m-i, n-j
for (int j=0; j<n; ++j) path[m-1][j] = 1;
for (int i=0; i<m; ++i) path[i][n-1] = 1;
for (int i=m-2; i>=0; --i) {
for (int j=n-2; j>=0; --j) {
path[i][j] = path[i+1][j] + path[i][j+1];
}
}
return path[0][0];
}
Method 2： stat
Need to take (m-1) + (n-1) steps in total, meaning number of ways = Choose (m-1) from (m+n-2);
