DP --- aggrated score

Score combination

America football rules
safty 2 points
field goal 3 points
touchdown 7 points

To get to a point S, how many possible combinations can happen.

It is graph, starting from 3 possible points 2, 3, 7, and each has three possible path to +2, +3, +7,  and so on. in the end. the score has to be s.

It is the same as find a path in the graph such that the path sum is s.

Solve:

> * 整理知识，学习笔记
> * 发布日记，杂文，所见所想
> * 撰写发布技术文稿（代码支持）
> * 撰写发布学术论文（LaTeX 公式支持）

computing the binorminal coefficient

n(n-1)..(n-k+1) / k(k-1)..2

$\frac{1}{2}$

First thinking is to do reduction of fraction on the nominator for each denominator.
Store a array of n, n-1, .., n-k+1,
and another array k, k-1, ..2,
Acutally since every two continuous numbers must have one has factor to 2
    every three continuous numbers must have one has factor to 3
and so on,maybe we can get a algorithm to find those numbers have i as factor easily

Actually since  14*13*12*11*10*9*8*7*6*5*4*3*2
the even number after divide by two is  7, 6,5,4,3,2, hence starting from  (n-k+1), it has factor (n-k+1)/2, (n-k+1)/2+1, (n-k+1)/2 +2.....for even numbers starting from (n-k+1)



use the equation  (n k) = (n-1 k) + (n-1 k-1)
Two dimentional DP, result in O(nk) complexity.

Pretty Printing --- DP

Break texts into lines, each line no more than L characters.
Messness is measured as the blanks in each line, (suppose n) then sum 2^n together for all the line inlcuding the last line.

Code:

int find_pertty_printing(const vector &W, const int &L)
{
    //calculate M(i)
    vector M( W.size(), numeric_limits::max() );
    for (int i=0; i    {
        int b_len = L - W[i].size();
        M[i] = min( (i-1<0 b_len="" case="" for="" i-1="" i="" line="" m="" occupy="" one="" p="" the="" when="" word="">        for (int j=i-1; j>=0; --j)
        {
            b_len -= ( W[j].size() + 1);
            if (b_len < 0) break;
            M[i] = min( (j-1<0 0="" :="" b_len="" case="" for="" i="" j-1="" line="" m="" multiple="" occupy="" one="" p="" when="" word="">        }
    }

    // find the minimum cost without considering the last line
    long min_mess  = ( W.size() >= 2 ? M[W.size() - 2] : 0);
    int b_len = L - W.back().size();

    for (int i=W.size() - 2; i>=0; --i)
    {
        b_len -= (W[i].size() + 1);
        if (b_len <0 min_mess="" nbsp="" p="" return="">        min_mess  = min( min_mess, (i-1<0 0="" :="" i-1="" m="" p="">    }
    return min_mess;
}

word breaking --- DP

Given a dictionary and a URL, break URL into several keywords, if possible.
e.g., bedbathandbeyond into bed bath and beyond, also bed bat hand beyond

Classical DP:
actually very simple DP, only need to check if T[j] is one, then S[j+1...i] is a word or not

Code:
vector word_breaking(const string &s, const unordered_set &dict)
{
   vector T(s.size(), 0);
   for (int i=0; i   {
       // set T[i] if s(0,i) is a valid word
       if (dict.find(s.substr(0, i+1)) != dict.cend() ) T[i] = i+1;
     // set T[i] if T[j]!=0 and s(j+1, i) is a valid word
       for (int j=0; j          if (T[j]!=0 && dict.find( s.substr(j+1, i-j))!=dict.cend() )
               T[i] = i-j;
   }

   vector ret;
   if ( T.back() )
   {
       int idx = s.size() - 1;
       while(idx >=0)
       {
           ret.emplace_back(s.substr(idx - T[idx] +1 , T[idx]) );
           idx  -= T[idx];
       }
       reverse(ret.begin(), ret.end());
   }
return ret;
}

Edit distance variations

1. Longest subsequence of A and of B
    Let the E(A,B) be 1. when A[i] = B[j] , 1+previous distance
                                2. when A[i]!=B[j] ,  0
  and the biggest one in the matrix, or record the maximum in one array D, is the longest subsequence.

2. Minimum number of characters need to delete to make A a palindrome
   Put all A's character in reverse order,  and get the min distance, then this distance is to make A a palindrome.


3. Given a string A and a regular expression, what is the string in the regular expression r that is closesst to A?

Need to change the comparing function stores in the matrix to regular expression

Edit distance ---- Minimum number of edits needed to transform the first string into the second string

Levenshtein distance:
either insert, delete, or substitute.

Suppose the length of A and B are a and b. and their distance is E(A,B)
There are two cases:
A[a-1]== B[b-1]    -------E(A[0...a-1],B[0...b-1])  = E(A[0...a-2], B[0...b-2])
A[a-1]!= B[b-1]   ------- E(A[0...a-1],B[0...b-1])  = 1 + min ( E(A[0...a-2],B[0...b-2]), E(A[0...a-1],B[0...b-2]), E(A[0...a-2],B[0...b-1])  ), viz., all three cases can happen, but we choose the minimum one.

C++:
iota(D.begin(), D.end(), val)   assign value to D from val and ++val everytime

The easy way is to implement it as a two dimentional maxtrix D. but here it is a ONE dimensional array.
Notice that at each step: we need to update the D[0] to i, and store D[i-1][j-1] (which is previous D[j-1])

Code:

int LevenDistance(string A, string B)
{
    if (A.size() < B.size())  swap(A,B);
    vector D( B.size()+1 );
    iota(D.begin(), D.end(), 0);

    for (int i=1; i<=A.size(); ++i)
    {
        int pre_i_1_j_1 = D[0];
        D[0] = i
        for (int j=1; j<=B.size(); ++j)
        {
            int pre_i_1_j = D[j];
            D[j] = A[i-1] == B[j-1] ? pre_i_1_j_1 : 1 + min( pre_i_1_j_1, min(D[j-1], D[j]) );
            pre_i_1_j_1 = pre_i_1_j;
        }
    }
    return D.back();
}

Determine whether an array S appear in a matrix A

std::tuple<int,char> mytuple (10,'a');

  std::get<0>(mytuple) = 20;

if S appears in A, there is a path.

This problem is about how to store the path already visited.

Naive thinking is to store 4 directions, since for each A[i][j], it has four neighbor to traversal. and there are 4! possiblities.

Clever way is to store a tuple {i, j, idx} where idx is the element position in S. 

and do four direction recursive.

When the tuple is in the set, means this element has been detected before.

Hence this result in a complexity of O(MNL) where M*N is the matrix size and L is the length of S.

C++: tuple initialization

 tuple tmp(i,j,len);

Solution:

class HashTuple
{
public:
    size_t operator() (const tuple &t) const
    {
        return hash()(get<0>(t)) ^ hash()(get<1>(t)) ^ hash()(get<2>(t)) ;
    }
};

bool match_helper(const vector > &A, const vector &S, unordered_set, HashTuple> cache,
                  int i, int j, int len)
{
     if (S.size()==len)  return true;

     tuple tmp(i,j,len);

     if (i<0 i="">=A.size() || j<0 j="">=A.size() || cache.find( tmp )!= cache.cend())
            return false;

     if (A[i][j] == S[len] && (match_helper(A, S, cache, i-1, j, len+1) ||
                               match_helper(A, S, cache, i+1, j, len+1) ||
                               match_helper(A, S, cache, i, j-1, len+1) ||
                               match_helper(A, S, cache, i, j+1, len+1) ))
                                return true;
    cache.insert(tmp);
    return false;
}

bool match(const vector > &A, const vector &S)
{
    unordered_set, HashTuple> cache;
    for (int i=0; i

Find the largest 2D subarray containing only 1's --- Dynamic Programming

Precedence of  Conditional operator ? : is from right to left.

Solution:
Hint: think how to change this problem to multiple problem of the largest rectangle under the skyline.

Simply think about each row as a x-axis, but what is the y-axis value of each row? For each column index in one row, it is the number of continuous 1' in that column above the row. Then for each row, we construct a skyline problem. solving it and compare each row, we can get this problem solution for O(NM), suppose N is the number of rows and M is the number of column.

Code:

int max2Dsubmatrix(const vector< vector > &A)
{
    vector > table; //record the skyline profile
    for(int i=0; i        for (int j=0; j    {
        if (A[i][j]!=0)
        {
            if(i-1 < 0) table[i][i] =1;
            else
                table[i][j] = table[i-1][j]+1;
        }
        else
            table[i][j]=0;
    }
    int max_rectange=0;
    for(const vector &t : table)
        max_rectange = max ( max_rectange, LargetRectangle(t));

    return max_rectange;
}

The area of largest rectangle constained in a skyline --- Dynamic Programming

Use "efficient frontier" method.
Basic idea is for each i, go left and right to find the first index j whose value A[j] is smaller than A[i], then the rectangle contained in the skyline is covered by the left and right value.
Use stack to store the compare information. It has complexity O(N),


It is a classical DP problem start from the middle and go both ways.

Code:

int LargetRectangle(const vector &A)
{
   stack stk;
   vector L;

   for(int i=0; i   {
       while(!stk.empty() && A[stk.top()]>=A[i])  stk.pop();

       L.push_back( stk.empty() ? -1 : stk.top()  );

       stk.push(i);
   }

   while(!stk.empty())  stk.pop();

   vector R(A.size());
   for(int i=A.size()-1; i>=0; --i)
   {
       while (!stk.empty() && A[stk.top()] >= A[i]) stk.pop();
       R[i] = stk.empty() ? A.size():stk.top();
       stk.push(i);
   }

   int max_area =0;
   for(int i=0; i   {
       int temp  = A[i]*(R[i]-1-L[i]-1+1);
       max_area = temp > max_area ? temp : max_area;
   }
    return max_area;
}

DP --- Longest subarray whose sum <= K

Can still be solved using the recording sequence method, but also need another sequence to record the sum along the sequence.

C++ standard library:
partial_sum():
example: partial_sum (val, val+5, result);

partial_sum (val, val+5, result, std::multiplies<int>());

back_inserter: example: copy (bar.begin(),bar.end(),back_inserter(foo)); insert bar.begin() to bar.end() to the back of foo. If foo =[1 2 3] bar = [ 3 2 1], then foo = [1 2 3 3 2 1 ]

std::vector<int>::iterator low,up;
low=std::lower_bound (v.begin(), v.end(), 20); //first element smaller than 20
up= std::upper_bound (v.begin(), v.end(), 20); //first element bigger than 20 

The solution is based on following theory:
Let R[i] be partial sum, and T[i] = min(R[k]) for k=i to k=N-1, so T[i] is monotonically increasing.

Consider any index i. Let j be the largest index such that T[j]<=k+R[i]. We claim that longest subarray starting at i+1 that has a sum less than or equal to k must end at j, inclusive.

The solution is to find the longest alone all i.

Solution:

pair partialsum(const vector &A, const int k)
{
    vector parsum;
    partial_sum(A.cbegin(), A.cend(), back_inserter(parsum));

    vector minParSum(parsum);
    for(int i=minParSum.size()-2; i>=0; --i)
        minParSum[i] = min( minParSum[i], minParSum[i+1] );

    pair arridx(0, upper_bound(minParSum.cbegin(), minParSum.cend(), k) - minParSum.cbegin() - 1 );

    for(int i=0; i    {
        int idx = upper_bound(minParSum.cbegin(), minParSum.cend(), k+parsum[i]) - minParSum.cbegin() - 1;
        if (idx - i - 1 > arridx.second - arridx.first)
        arridx = {i+1, idx};
    }
    return arridx;
}

Find the path along a binary tree where their node sums to a given value

Solution:
Key point is to know that the path is at most the height of the tree. Hence, need to find the height to the tree first.
Then use a path array to store the node value along the path
Then use recursive to go left and right to see whether we can find the sum and check sum at each point of the path

DP --- Longest Non-decreasing Subsequence

1. Find the longest alternating subsequence
   ai < ai+1 for even i, ai > ai+1 for odd i

   can still use the record the longest sequence method, just need to pay attention where to put the new element

2. Define a sequence of points in the plane to be ascending if each point is above and to the right of the previous point. How would you find a maximum ascending subset of a set of points in the plane?
First map them to the x-axis, then get the height of each point sqrt(x^2+y^2) , then do the same non-decreasing subsequence

DP --- Longest Nondecreasing Subsequence

1. Classical DP, finding the longest nondecreasing subsequence can also used in like string matching, analyzing card games.
The point is to remember the length of previous longest subsequence at each point.
This method gives O(N^2) complexity, since for each n, we need to check all previous values length, then find the maximum

2. This method is O(NlogN). Basic idea is to keep a array to store the longest subsequence, if the A[i+1] is bigger than all then put it at behind, if A[i+1] is not bigger than all then update it in the subsequece, since it forms a non-decreasing subsequence, although not have the length of the array.

Code:

int longestSub(const vector &A)
{
    vector tail_value;
    for(const int &a : A)
    {
        auto it = upper_bound(tail_value.begin(), tail_value.end(), a);
        if (it == tail_value.end()) tail_value.push_back(a);
        else   *it = a;
    }
    return tail_value.size();
}

DP --- Maximum Subarray Sum in Circular Array

1. For each i, find the maximum subarray sum from 0 to i-1, viz. Si, and the maximum subarray sum from i to      N-1, viz., Ei, the maximum subarray sum for the circular array is maximum of Si+Ei  and compare it with non circular case
 Question:
       how do they know Si+Ei is a continuous subarray?
Answer:
       cause Si is not a subarray sum , it is the partical sum from 0 to anywhere smaller than i

2. Find the minimum subarray sum, since either min or max will cover the cross over of 0 and N-1,

3. Doing non circular finding subarray sum for 2N array, but need to consider the length

For non circular version:
1. Partial sum  - min sum
2. Maximum till i  = max (A[i], max till i ) and maximum sum


Code:

int maxSumNonCirular(const vector &A)
{
    int Mxtil =0;
    int Mx =0;

    for (int i=1; i    {
        Mxtil = max(A[i], A[i]+Mxtil);
        Mx = max(Mx, Mxtil);
    }
    return Mx;
}

int maxCircular(const vector &A)
{
    vector maxBegin;
    int sum = A.front();
    maxBegin.push_back(sum);
    for (int i=1; i    {
        sum+=A[i];
        maxBegin.push_back( max (maxBegin.back(), sum));
    }

    vector maxEnd(A.size());
    sum =0;
    maxEnd.back()=0;
    for (int i=A.size()-2; i>=0; --i)
    {
        sum+=A[i+1];
        maxEnd[i] = max( maxEnd[i+1], sum);
    }

    int cirMax =0;
    for (int i=0; i    {
        cirMax = max(cirMax, maxBegin[i]+maxEnd[i]);
    }
    return cirMax;
}

int maxSubArrayCircular(const vector &A)
{
    return max( maxSumNonCirular(A), maxCircular(A) );
}

DP --- Maximum Subarray Sum

Finding maximum subarray sum

Solution1;
Since the subarray with maximum sum can happen anywhere of an array, even if we know the maximum subarrary sum for A[0]...A[n-1], we don't know how to use it to derive a maximum subarray sum for A[0]...A[n].

This problem has to think about the relation of A[0]...A[n-1] and A[0]...A[n] in terms of subarray. Suppose the sum ending at i is S[i], then when A[n] is added, the possible biggest subarray ending at A[n] is S[n] - min(S[i]) for 0<=i<=n-1. Compare it with  recording maximum subarray sum ending at A[n-1], we can get maximum subarray sum ending at A[n].

Complexity is O(N), space usage is O(1)


Solution 2:
Remeber the maximum subarray till A[i], it is max(A[i], A[i] + maximum subarry till A[i-1]) , then the maximum subarray sum is max (previous max,  maximum till A[i])

Code:
For solution 1:
pair maxsubsum(vector  &A)
{
     int Min =  0;   // min S
     int Sum = 0;   // sum S
     int Max = numeric_limit::min();   //max
     pair range(0,0);
    int idx = -1;

    for (int i=0; i   {
         Sum += A[i];
         int temp = Sum - Min;
          if (Sum < Min) {Min = Sum; idx = i;}
         if (temp > Max)
                 {Max =  temp; range = {idx+1, i+1}
    }
     return range;
}

Dynamic Programming

    DP is a general technique for solving complex optimization problems that can be decomposed into overlapping subproblems. Like divide and conquer, we solve the problem by combining the solutions of multiple smaller problems but what makes DP different is that the subproblems may not be independent. A key to making DP efficient is reusing the results of intermediate computations. Problems which are natually solved using DP are a problem choice for hard interview questions.
     The simplest DP probably is the solving Fibonacci number defined by Fn=Fn-1+Fn-2. If we don't store the Fn value, we need to compute Fn many times. 
The key to solving any DP problem efficiently is finding the right way to break the problem into subproblems such that 
--- the bigger problem can be solved relatively easily once solutions to all the subproblems are available, and 
--- you need to sovle as few subproblems as possible
In some cases, this many require solving a slightly different optimization problem than the original problem. 

Find the common ancestor of two tree nodes

If there is parent pointers, trace back along the parent pointers and when those two parents intersect, that is the common ancestor. But this need a table for visited nodes.

If there is no parent pointers, when those two nodes are at the different sides of a node, that node is the common ancestor, otherwise, they are at the same side (left or right) of a node.

Code:
bool cover(TreeNode* root, TreeNode* p)  // check whether p is a node in the tree
{
    if (root==NULL) return false;
    if (root==p) return true;

    return cover(root->left, p) ||  cover(root->right, p);
}

TreeNode* checkhelper(TreeNode* root, TreeNode* p, TreeNode* q)
{
    if (root==NULL) return NULL;
    if (root==p || root==q) return root;

    if (  cover(root->left, p)!=cover(root->left, q) ) return root;
    TreeNode* childnode;
    childnode = cover(root->left,p) ? root->left : root->right;
    return checkhelper(childnode, p, q);
}

TreeNode* commonancestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
    if (root==NULL) return NULL;
    if ( !cover(root,p) || !cover(root,q) ) return NULL;
    return checkhelper(root, p,q);
}

Optimized version:

Find the "next" node in a in-order traversal of a given node

Since it is in-order traversal, the next node is the node with the next big value.
There are many cases to think about. But in all, it comes only two cases.
1. If the given node has right child, the next node is the left most child node of that right child.
2. If the given node has no right child, the next node is its upper parent where this node is reside in its left subtree. That is, go all the way up to find the first node whose left subtree has this node.

Code:
TreeNode* leftMostChild(TreeNode* node)
{
    if (!node) return nullptr;
    while(node->left)
    {
        node = node->left;
    }
    return node;
}

TreeNode* inorderSucc(TreeNode* node)
{
    if (!node) return nullptr;
    if (node->right)
    {
        return leftMostChild(node->right);
    }
    else
    {
        TreeNode* q = node;
        TreeNode* x = q->parent;

        while(x && x->left!=q )
        {
            q = x;
            x = x->parent;
        }
        return x;
    }
}

Determine whether a tree is balanced

Determine whether a tree is balanced.
Balance is defined as no two nodes has greater than one height.



Code:

use queue.size() to remember how many nodes at each layer (height)

// Iterative method to find height of Bianry Tree

int treeHeight(node *root)

{

    // Base Case

    if (root == NULL)

        return 0;

 

    // Create an empty queue for level order tarversal

    queue q;

 

    // Enqueue Root and initialize height

    q.push(root);

    int height = 0;

 

    while (1)

    {

        // nodeCount (queue size) indicates number of nodes

        // at current lelvel.

        int nodeCount = q.size();

        if (nodeCount == 0)

            return height;

 

        height++;

 

        // Dequeue all nodes of current level and Enqueue all

        // nodes of next level

        while (nodeCount > 0)

        {

            node *node = q.front();

            q.pop();

            if (node->left != NULL)

                q.push(node->left);

            if (node->right != NULL)

                q.push(node->right);

            nodeCount--;

        }

    }

}

Following method is to determine whether it is balanced


int checkheight(TreeNode* root)
{
    if (!root) return 0;
    int leftheight = checkheight(root->left);
    if (leftheight==-1) return -1;

    int rightheight = checkheight(root->right);
    if (rightheight==-1) return -1;

    int heightDiff = leftheight-rightheight;

    if ( abs(heightDiff) >1 )
        return -1;
    else
        return max(leftheight, rightheight) +1;
}

// check whether its is balanced tree
bool balancecheck(TreeNode* root)
{
    if(checkheight(root) == -1 )
        return false;
    else
        return true;
}