有趣的算法

算法之所以有趣星虹，在于他能夠化繁為簡零抬，他能概括統(tǒng)御世間萬物，將一個(gè)復(fù)雜的問題歸結(jié)為一個(gè)非常簡單的問題宽涌。其實(shí)所有高階的算法平夜，都可以用兩個(gè)大的方法去解決，而且屢試不爽卸亮。分別是動態(tài)規(guī)劃和貪心算法.
我們先從一道動態(tài)規(guī)劃的問題先說起吧忽妒。

動態(tài)規(guī)劃問題

最長公共子序列問題(LCS)，給定兩個(gè)序列X和Y兼贸，求他們之間最長的公共子序列段直。

哇，這題目感覺有點(diǎn)難啊溶诞。最長公共子序列問題其實(shí)可以歸結(jié)為最最最最最簡單的一個(gè)遞推表達(dá)式鸯檬，首先我們假設(shè)序列X元素個(gè)數(shù)為i，Y為j螺垢，C[i, j]表示最長公共子序列的長度喧务。好那么問題就變成了，如何求取這個(gè)最長公共子序列的長度問題枉圃。公式也是非常簡單 ==easy== :smile:

$$C[i, j] = \left{ \begin{array}{lr} 0,\quad if \ x=0 , or \ y=0 \ C[i-1, j-1] + 1, \quad if ; i,j>0 ; , x_i=y_i \ max{C[i, j-1], C[i-1, j]} , \quad if \ i,j>0, \ x_i\neq x_j \end{array} \right. $$

這個(gè)公式還是非常難打啊功茴，大概就是這么一個(gè)意思吧。咋一看這個(gè)表達(dá)式很牛逼啊讯蒲，你隨便給我兩個(gè)序列痊土，我通過他就可以求出最長子序列的長度？閑話不多說墨林，讓我們直接上代碼看一下到底有沒有這么牛逼赁酝。

假如我們有兩個(gè)序列，我們用字符串來表示吧 X=cnblogs, Y=belong, 肉眼可以看到最長子序列為blog旭等。那么長度就是4酌呆，讓我們看看到底有沒有這么牛逼。

在這之前搔耕，我得理清一下思路隙袁，首先是這樣的痰娱，我們求取的這個(gè)C[i, j]，實(shí)際上就是一個(gè)二維的矩陣菩收，你想啊i是從0變到i梨睁，j是從0變到j(luò)，那一路求過來娜饵，不就是一個(gè)i行j列的矩陣嗎坡贺？目標(biāo)值就是最右下角的這個(gè)元素。既然如此那么變成就好辦了箱舞。

// this code calculate the max length of common sub-sequence of 2 strings
int lcs_length(string a, string b) {
    // given 2 string, return the LCS length
    // define a 2 dim array
    int matrix[a.size()+1][b.size()+1];
    for (int i = 0; i <= a.size(); ++i) {
        matrix[i][0] = 0;
    }
    for (int j = 0; j <= b.size(); ++j) {
        matrix[0][j] = 0;
    }

    for(int i = 1; i <= a.size(); i++) {
        for(int j = 1; j <= b.size(); j++) {
            if (a[i-1] == b[j-1]) {
                matrix[i][j] = matrix[i-1][j-1] + 1;
            } else {
                matrix[i][j] = matrix[i][j-1] > matrix[i-1][j] ? matrix[i][j-1] : matrix[i-1][j];
            }
        }
    }
    return matrix[a.size()][b.size()];
}

很顯然遍坟，這個(gè)函數(shù)可以正確的得到最長公共子串的長度∏绻桑看上去還是很牛逼愿伴，但是其實(shí)道理也非常簡單，無外乎就是上面的三個(gè)公式电湘。那么你可能回問了隔节，上面三個(gè)公式是怎么來的呢？其實(shí)就是一個(gè)非常簡單的遞推胡桨，假如說公共子串Z的最后一個(gè)元素是X的最后一個(gè)元素官帘，那么肯定也是Y的最后元素瞬雹，那如果將X去掉最后元素昧谊，Y去掉最后一個(gè)元素，最長公共子串就是去掉之后的+1酗捌，就是加去掉的這個(gè)嘛呢诬。那如果說最后一個(gè)元素都不是X， Y的最后元素胖缤，那更好辦了尚镰，這個(gè)時(shí)候公共子串就是X和Y的中間某一個(gè)子串嘛，這個(gè)時(shí)候X去掉最后一個(gè)哪廓，再來求公共子串狗唉，還是一樣啊，或者Y去掉一個(gè)涡真，也是一樣啊分俯，就直接就等于X或者Y去掉一個(gè)的共同子串的最大值了。(有人會問哆料，為什么不等于X缸剪，Y都去掉一個(gè)的最大值呢？也就是 $$ max{C[i-1, j-1], C[i-1, j-1]}$$东亦， 這是不行的杏节，原因很簡單，你X去掉一個(gè)之后，最長子串就有可能包含Y的最后一個(gè)值了奋渔，你都去掉會減少很多種情況镊逝，不可取 )。

這個(gè)問題我們已經(jīng)完成了歷史性的一步： 可以求取兩個(gè)序列的最長子序列的長度嫉鲸。蹋半， 那么下一步就是，怎么找到這個(gè)最長子序列充坑。這一步思路是這樣的：

(你可能無法想象减江，我完成求最大公共子序列上調(diào)試C++代碼踩了一下午坑，我曹捻爷，真的是天坑)辈灼。先說一下思路吧，非常復(fù)雜也榄，首先在上面的函數(shù)里面我們給他傳入一個(gè)pFlag的二維數(shù)組巡莹，注意這是一個(gè)指針，因?yàn)楹竺嫘枰f歸遍歷他甜紫。在這個(gè)二維數(shù)組里面存儲的大小和matrix是一樣降宅，只不過這里面存儲的都是字符串，為了便于理解我存儲為 : “l(fā)eft", "up", "left_up"囚霸，三種字符串腰根，其實(shí)你如果自己畫了matrix這個(gè)表，就會發(fā)現(xiàn)拓型，其實(shí)可以通過這樣的箭頭去回溯這個(gè)最長子序列是什么额嘿，你會發(fā)現(xiàn)恰恰是箭頭所指向的路徑。然后我們用一個(gè)函數(shù)遞歸劣挫，根據(jù)箭頭來找到對應(yīng)的子序列册养。所有代碼如下：

#include <iostream>
#include <vector>
using namespace std;
void sub_sequence(int i, int j, string **pFlag, string a) {
    if (i == 0 || j == 0) {
        return;
    }
    if (pFlag[i][j] == "left_up") {
        sub_sequence(i - 1, j - 1, pFlag, a);
        cout << a[i-1] << " ";
    } else {
        if (pFlag[i][j] == "left") {
            sub_sequence(i, j-1, pFlag, a);
        } else {
            sub_sequence(i-1, j, pFlag, a);
        }
    }
}

int lcs_length(string a, string b, string **pFlag) {
    // given 2 string, return the LCS length
    // define a 2 dim array
    int matrix[a.size()+1][b.size()+1];
    for (int i = 0; i <= a.size(); ++i) {
        matrix[i][0] = 0;
    }
    for (int j = 0; j <= b.size(); ++j) {
        matrix[0][j] = 0;
    }
    for(int i = 1; i <= a.size(); i++) {
        for(int j = 1; j <= b.size(); j++) {
            if (a[i-1] == b[j-1]) {
                matrix[i][j] = matrix[i-1][j-1] + 1;
                // using string to indicate location
                pFlag[i][j] = "left_up";
            } else {
                if (matrix[i][j-1] > matrix[i-1][j]) {
                    matrix[i][j] = matrix[i][j-1];
                    pFlag[i][j] = "left";
                } else {
                    matrix[i][j] = matrix[i-1][j];
                    pFlag[i][j] = "up";
                }
            }
        }
    }
    return matrix[a.size()][b.size()];
}

int main()
{
    string b = "gheteuponthiop";
    string a = "giothuphyo";
    // 這里應(yīng)該是**pFlag, markdown渲染有問題，二維指針
    auto ** pFlag = new string* [a.size() + 1];
    for (int k = 0; k <= a.size(); ++k) {
        pFlag[k] = new string[b.size() + 1];
    }
    int l = lcs_length(a, b, pFlag);
    sub_sequence((int) a.size(), (int) b.size(), pFlag, a);
    cout << endl;
    cout << l << endl;
    return 0;
}

收工压固！以后遇到求最大公共子序列問題就來我的博客Ｇ蚶埂！Ｕ饰摇坎炼！

寫到這里發(fā)現(xiàn)并不是那么有趣了。很復(fù)雜啊焚刚。点弯。。不過堅(jiān)信那句矿咕，萬變不離其宗抢肛。