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

机智的办法，再揣摩
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);