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();
}