Chapter 7 Recursion and Dynamic Programming

"The Rules"

乘法原理和加法原理

1.Build approach from subproblems to the final destination。
这类问题的keyword： compute the nth, visit the first n, return all paths, etc
凡是解决此类问题，无非只有两种方法，Bottom-Up 与 Top-Down， 形式上前者对应iteration, 后者对应recursion。

本文将问题节点空间"两端收敛"的问题，归结为收敛结构，通常这类问题的path也为“有限”个，例如: n!, fibnacci(n)；将节点空间"发散"的问题，归结为发散结构，例如: 二叉树的遍历。 抽象地说，能够在多项式时间内解决的问题，是收敛问题（P类问题），不能在多项式时间内解决的问题（如阶乘级或指数级），是发散问题。（关于P问题的描述：http://www.matrix67.com/blog/archives/105 ）

特别地，聚合问题(Aggregate)，即关于特解（包括判定性问题） 或最优解或总和的问题，具有很强的收敛性质。

2.Recursion的空间与时间成本
对系统来说，一般利用底层stack实现递归。每次操作可视为stack里的一个object。
递归的 time cost 随 $n$ 成指数增长，其中 $n$ 为递归的深度（单路径递归调用的次数）; space cost为 $O(n)$。

3.算法策略
Divide and conquer : 将问题分成几个部分，每一部分问题互相不重叠，假定每个部分都可以得到解决进行递归调用，合并每一部分的结果。例如Merge Sort,Quick Sort。

Dynamic Programming：尽可能不重复计算每个subproblem，将计算结果存储下来，以确定后驱问题的结果。与贪心算法的区别是，在计算后驱问题时，可能会综合考虑多个前驱问题的解。

Greedy Algorithm : 只做出当下最优的判断，从全局来说并不能保证总是最优。如Dijkstra算法。

Backtracking： 一种暴力（穷举）的深度优先搜索法，直至检索到节点空间的尽头。Tree或Graph的DFS，是backtracking的special case。
http://stackoverflow.com/questions/6162465/divide-and-conquer-dynamic-programming-and-greedy-algorithms

模式识别

1.用Dynamic Programming(Bottom-Up) 解决收敛结构问题

具有强收敛性的问题（例如关于特解或最优解或数量总和的问题，所有的判定性问题），问题对应的N维有限空间中的节点可以用整数坐标表示， 且当前节点的解只依赖于前驱节点（无论顺序还是倒序），那么往往可以用dynamic programming解决。解决的关键是建立subproblem的解之间的递推关系，也就是当前节点由前驱节点决定, 然后将当前节点的解（或往往是，以当前节点为末节点的解，抑或是以当前两个节点为头尾的序列的解）用array记录下来（如果当前节点只由之前紧接的若干个节点决定，那么也可以只用若干个变量）。

$f(n) = G(n, f(n-1) , f(n-2) , ... , f(1) )$ 或

$f(i,j) = G[ f(i-1,j -1), f(i,j-1), f(i-1,j) ]$

处理时以问题的一端为循环开端，以另一端为循环终止条件( 两端均为收敛），记录部分或全部解（DP Table。如int cache[n] )，DP Table的下标即为递推关系中的函数参数。

如果除到达终点外还需记录具体的path，则可记录前驱节点prev[n] 或 vector<vector<int> > prev，然后用backtracking处理成path。只不过，这时候backtracking经过DP的剪枝，只剩下正确的路径。因此这时候判断非法节点和胜利条件通常是等价的。

e.g.1 Climbing takes n steps to reach to the top. Each time you can either climb 1 or 2 or 3 steps. In how many distinct ways can you climb to the top? ( CtCI 9.1 ,Leetcode: Climbing Stairs）
e.g.2 Compute the Nth prime ( Ebay interview )
e.g.3 Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. ( Leetcode: Word Break )
e.g.4 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. (Leetcode:Palindrome Partitioning II)

特别地，具有简单“聚合”性质的问题，如最值或求和问题，往往可以进一步优化DP Table的空间。更确切地说，是那些只在乎紧邻的前一个最优解，而不在乎前几个最优解的问题（这样的话，就可以接受每次替换掉那个最优解，在这个维度上只用O(1)的空间）最简单的例子就是求一个数组内数的最值/求和(到目前为止的解是到之前一个的解以及当前的值综合的结果)。

e.g.1 How many paths are there for the robot to go from $(0,0)$ to $(x,y)$ ( CtCI 9.2, Leetcode: Unique Path)

e.g.2 Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? (GeeksforGeeks: http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/ )

e.g.3 Please implement a function which gets the minimal number of coins, whose value is v1, v2, …, vn, to make change for an amount of money with value t. Any coin with value vi may duplicate for any times to make change. (http://codercareer.blogspot.com/2011/12/no-26-minimal-number-of-coins-for.html)

对于“最长子序列”问题（即求解有限空间内，满足一定条件的最长顺序节点序列），用DP Table来记录以当前节点为末节点的序列（而不是以当前节点或之前节点为末节点的序列）的解，并根据递推关系，由问题空间的起点到达问题空间的终点。注意，对于"回文"序列，中间节点可以等效为序列的末节点。

e.g.1 Longest increasing subsequence of an array.
e.g.2 Given the heights of each person in the circus, compute the largest possible number of people in tower. ( CtCI 11.7)
e.g.3 Find the contiguous subarray within an array (containing at least one number) which has the largest sum. ( Leetcode: Maximum Subarray, CtCI 17.8 )
e.g.4 There are N gas stations along a circular route, where the amount of gas at station i is gas[i].You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations. Return the starting gas station's index if you can travel around the circuit once, otherwise return -1. (Leetcode: Gas Station)

e.g.5 Longest Common Subsequence ( http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/)

特别地，如果当前节点的解既依赖于前驱子问题，又依赖于后驱子问题，，则可考虑先顺序遍历，记录DP Table，再倒序遍历，合并DP Table的解。

e.g.1 Say you have an array for which the ith element is the price of a given stock on day i.Design an algorithm to find the maximum profit. You may complete at most two transactions.(Leetcode: Best Time to Buy and Sell Stock III)
e.g.2 Replace each element with the product of all elements other than that element.(Ebay Interview)
e.g.3 Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.( Leetcode: Trapping Rain Water)

2.用Memoization Technique（Top-Down）解决收敛结构问题

hash的读取写在计算前，hash的储存写在计算后。

对于弱收敛性问题（例如“满足特定条件的所有解"），如果胜利条件只取决于当前节点与后驱节点，而与前驱节点无关，并且subproblem有overlap，那么可以利用memoization technique来进行递归, 即以局部解为递归的返回值，并且记录当前计算的局部解（以当前的函数参数为key，函数的返回值为value）。Memoization是Top-Down形式的Dynamic Programming，并且受到的制约更少，自然也可以用来解决强收敛性问题（但空间上可能效率不及Bottom-Up形式的DP）。

e.g.1 Build the tallest stack of boxes, if each box is larger than the box above it in any dimension(CtCI 9.10)

vector<Box> createStackDP( Box boxes[],const int num, Box bottom, map< Box, vector<Box> >& stackCache){
    vector<Box> max_stack;
    int max_height = 0;
    vector<Box> new_stack;
    if( stackCache.count( bottom ) > 0 )
        return stackCache[ bottom ];
    else{
        for( int i = 0; i < num; i++ ){
            if( Box[i].canBeAbove( bottom ) ){
                new_stack = createStackDP( boxes, num, Box[i], stackCache );
            }
            if( new_stack.size() > max_height ){
                max_height = new_stack.size();
                max_stack = new_stack;
            }
        }
    }
    max_stack.insert( max_stack.begin(), bottom );
    stackCache[ bottom ] = max_stack;
    return max_stack;
}

e.g.2 Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. ( Leetcode: Word Break II)

class Solution {
public:
    vector<string> wordBreak(string s,unordered_set<string> &dict,unordered_map<string,vector<string> >& cache){
        if(cache.count(s))
            return cache[s];
        vector<string> vs;
        if(s.empty()){
            vs.push_back(string());
            return vs;
        }
        for(int len = 1; len <= s.size(); ++len ){
            string prefix = s.substr(0,len);
            if(dict.count(prefix) > 0){
                string suffix = s.substr(len);
                vector<string> segments = wordBreak(suffix,dict,cache);
                for(int i = 0; i < segments.size(); ++i){
                    if(segments[i].empty()) vs.push_back(prefix);
                    else vs.push_back(prefix + " " + segments[i]);
                }
            }
        }
        cache[s] = vs;
        return vs;
    }
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(s.empty()) return vector<string>();
        unordered_map<string,vector<string> > cache;
        return wordBreak(s,dict,cache);
    }
};

3.用Backtracking( Top-Down )解决发散结构问题

对于发散性问题（例如“所有组合"，"全部解"），可以选取其问题空间"收敛"的一端作为起点，沿着节点发散的方向（或者说，当前决策的多种选择）递归，直到a.当前节点"不合法" 或 b.当前节点发散方向搜索完毕才会return。所谓"剪枝"(pruning)，就是指只选择尽可能少的、可能到达"胜利条件"的方向， 例如将幂指数级的复杂度降低到阶乘级。注意如果经过剪枝之后，所有搜索只会沿着"正确"的方向行进，那么当前节点"不合法"往往也就意味着胜利条件。

如果需要记录决策的路径，可以用vector<int> &path沿着搜索的方向记录，在满足胜利情形时记录当前path。注意在return前，删除path中的当前节点。如果搜索的方向有出现环路的可能，那么可以使用bool []或unordered_map来记录该节点是否已被使用，只要注意在访问时以及return前维护即可(TODO? 需要在访问下一个节点之前记录)。TODO: 换句话说，如果backtracking可能会回到原点，那么需要用visited table去记录哪些被访问过，否则就会infinite loop或recursion
e.g.1 Graph BFS, DFS
e.g.2 841. Keys and Rooms TODO : A*启发式搜索
e.g.3 https://leetcode.com/problems/sliding-puzzle/

Backtracking办法的典型模板：

void backtracking( P point, vector<P> &path, vector<vector<P> >&paths ）{
        if（!point )  // invalid point
            return;
        path.push_back(point);
        bool success =  ;  // condition for success
        if( success )  
            paths.push_back( vector<P>(path.begin(),path.end()) ); // don't return here
        for( P next: all directions )
            backtracking( next, path, paths );
        path.pop_back();
        return;
}

e.g.1 Given n pairs of parentheses, generate all combinations of parentheses. ( CtCI 9.6, Leetcode:Generate Parentheses)

class Solution {
public:
    void gP(int leftRem, int rightRem, string &path, vector<string> &paths ){
        if(leftRem < 0 || rightRem < 0)
            return;
        if(leftRem > 0){
            path.push_back('(');
            gP(leftRem-1,rightRem,path,paths);
            path.pop_back();
        }
        if(leftRem < rightRem){
            path.push_back(')');
            if(rightRem == 1)
                paths.push_back(path);
            gP(leftRem, rightRem-1,path,paths);
            path.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        if(n == 0)  return res;
        string path;
        gP(n,n,path,res);
        return res;
    }
};

e.g.2 Implement the "paint fill" function that fill in the surrounding area until the color changes.( CtCI 9.7 )

enum Color{
    white,yellow,green,blue,black
};
void paintFill( int **screen, int m, int n, int x, int y, Color ncolor){
    if( x >= n || x < 0 || y >= m || y < 0 )
        return;
    if( screen[y][x] != ncolor){
        screen[y][x] = ncolor;
        paintFill( screen, m, n, x +1,y, ncolor);
        paintFill( screen, m, n, x ,y +1, ncolor);
        paintFill( screen, m, n, x -1 ,y , ncolor);
        paintFill( screen, m, n, x ,y -1 , ncolor);
    }
}

e.g.3 Placing n queens on an n×n chessboard such that no two queens attack each other. ( CtCI 9.9, Leetcode: N-queens)

bool checkValid( int row1, int col1,int *rowCol ){
    for( int row2 = row1 - 1; row2 >= 0; row2--){
        if( rowCol[row2] == col1 )
            return false;
        if( abs(row1 - row2) == abs( rowCol[row2] - col1 ) )
            return false;
    }
    return true;
}
void placeQ( int row, int rowCol[], vector<int*>& res ){
    if (row == GRID_SIZE){
        int *p = new int[GRID_SIZE];
        for( int i =0; i < GRID_SIZE; i++)
            p[i] = rowCol[i];
        res.push_back(p);
        return;
    }
    int col = 0;
    for(col = 0; col < GRID_SIZE; col++){
        if( checkValid(row,col,rowCol) ){
            rowCol[row] = col;
            placeQ( row+1, rowCol,res);
        }           
    }   
} 

e.g.4 Solve a boggle game, with a dictionary given as unordered_set. （Ebay Interview )

处理收敛结构问题，如果无论从哪一端出发，都避免不了"（部分）当前节点的解依赖后驱节点"（也就是说，当前节点，如果不能获知后驱节点，就无法得到有意义的解），那么可以也用backtracking解决。（参见Chapter 3）

4.用Divide and Conquer 解决独立子问题
如果能将问题分成若干个部分解决，且互相孤立，则可以优先选择使用D&C策略。特别地，如果期望将问题的复杂度由$O(n)$进一步降低（$O(logn)$），一般总是可以联想到使用D&C策略，将问题分割而治。

e.g. 1 Implement pow(x, n). (Leetcode: Pow(x, n) )

double pow(double x, int n) {
    if (n == 0) return 1.0;
    if( abs(x) < numeric_limits<double>::epsilon() )
        return 0.0;
    double half = pow(x,n/2);
    if(n%2 == 0)
        return half*half;
    else if(n > 0)
        return half*half*x;
    else
        return half*half/x;
}

e.g.2 Divide two integers without using multiplication, division and mod operator. (Leetcode:Divide Two Integers; EPI: 5.14 )

class Solution {
public:
    int divide(int dividend, int divisor) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        int sign = 1;
        if(divisor == 0) throw overflow_error("Divide by zero exception");
        if(dividend < 0) sign = -1;
        if(divisor < 0 ) sign = -sign;
        long long y = abs((long long)dividend);
        long long x = abs((long long)divisor);
        int power = 0;
        while( (x<<power) <= y )
            power++;
        long long res = 0;
        while( y >= x ){                    //divide the problem into dealing with every bit
            if( y >= x<<power ){
                y -= x<<power;
                res |= 1<<power;
            }
            power--;
        }
        if(sign == -1) return -res;
        else    return res;
    }
};

e.g. 3 Evaluate an infix notation( without parentheses ). ( Ebay interview question ).

double readNum( char * &str){
    double num;
    sscanf( str, "%lf", &num );
    str++;
    while( isdigit(*str) || *str == '.' )
        str++;
    return num;
}
double evaluate( char *str){
    if( *str == '\0' )
        return 0.0;
    double res = 1.0;
    char op = '*';
    while( op == '*' || op == '/' ){
        if( op == '*' )
            res *= readNum(str);
        else
            res /= readNum(str);
        op = *str++;
    }
    return res + evaluate( --str);
}