前言

背包問題

本文鏈接前文：背包問題在下面的鏈接
【演算法】用習題教你如何使用動態規劃，超詳細，一看就會！！建議收藏！！

今天這篇來跟大家看看編輯問題與不同的子序列 --廢話不多說，我們開始吧！

一、編輯問題

LC77 編輯距離

文章概述：給定兩個單詞word1和word2，請計算將word1轉換為word2至少需要多少步操作，
你可以對一個單詞執行以下3種操作：
a）在單詞中插入一個字符
b）洗掉單詞中的一個字符
c）替換單詞中的一個字符

例子 從word1：abc 到 word2： egh

拿到這道題目大家開始想的是什么呢？
首先：根據上文，我們首先要想辦法弄清楚狀態的定義是什么樣的會方便后面的求解，
我們先來思考一下：狀態的定義如果設定為在word1中前i個字符轉換為word2的次數，–我們可以利用這個狀態再去添加字符經過一次變換得到次數嗎？是不行的，因為我們沒辦法知道我們添加的字符是否能夠構成word2
所以我們這里的狀態定義定義成word1的前i個字符經過這三種操作轉換成word2的前j個字符，即：F(i,j):word1的前i個字符于word2的前j個字符的編輯距離

有了狀態的定義，狀態的轉換我們又得思考一番了，F(i,j) = ??
我們知道每個單詞可以進行三種操作，插入，洗掉，替換
我們逐一解釋：
什么時候需要插入？ 這時F(2,1)- -即F（i, j-1） 即從ab -->e ,F(2,2) =F(2，1)+插入word2的第j個字符,這里的 ab已經轉換為了e，我們需要添加一個g給他，即F(2,2)比起F（2，1）的編輯次數多了一次，F（i，j）=F(i , j- 1)+1
什么時候需要洗掉？ F(1，2) - -即F（i -1 ，j） 即從a–>eg, F(1,1) =F(1,2)+洗掉word1的第i個字符 ，因為這時的F(1, 2)已經轉換為了兩個字符，所以我們這里的F（1，1）就是在F（1，2）的基礎上洗掉一個字符，F(i , j )=F(i-1 , j)+1，
什么時候需要替換呢？ F（i-1, j-1）這時我們的 F（i，j）=F（i-1，j-1）+1，但時需要考慮一種情況，當我們的word1的第i個字符和word2的第j個字符相等時，不需要替換操作，F（i，j）還是F（i-1，j-1）

分析到這里，狀態轉換F（i，j）究竟是什么很清楚了，我們每次操作一個字符，所以
F（i，j） = min（插入，洗掉，替換）
初始化：因為我們看到F（i，j）都可能需要 F（i-1，j）前一行，F（i-1，j-1）前一行一列，F（i，j-1）前一列的值，所以這個時候我們就多給一行一列，
F（i，0）：表示給word1的前i個字符到0個字符，即進行洗掉操作，有多少個字符洗掉多少個；
F（0，j）則表示插入操作，從0字符到j字符，插入j個字符
回傳結果就是F（S.szie(),T.size()），

class Solution {
public:
    /**
     * 
     * @param word1 string字串 
     * @param word2 string字串 
     * @return int整型
     */
    int minDistance(string word1, string word2) {
        // write code here
        int row =word1.size();
        int col =word2.size();
        //vv用來保存子結果
        vector<vector<int>> vv(row+1,vector<int>(col+1,0));
        for(int i =0;i<=row;++i)
        {
        //初始化
            vv[i][0] =i;
        }
        for(int j =0;j<=col;++j)
        {
        //初始化
            vv[0][j] =j;
        }
        for(int i =1;i<=row;++i)
        {
            for(int j =1;j<=col;++j)
            {
                //狀態轉換
                //插入洗掉中選一個
                vv[i][j] = min(vv[i-1][j]+1,vv[i][j-1]+1);
                if(word1[i-1] ==word2[j-1])
                    vv[i][j] = min(vv[i-1][j-1],vv[i][j]);
                else
                    vv[i][j] = min(1+vv[i-1][j-1],vv[i][j]);
                    
            }
        }
        //ret
        return vv[row][col];
    }
};

二、不同的子序列

LC36 不同的子序列

題目描述：
給定兩個字串S和T，回傳S子序列等于T的不同子序列個數有多少個？
字串的子序列是由原來的字串洗掉一些字符（也可以不洗掉）在不改變相對位置的情況下的剩余字符（例如，"ACE"is a subsequence of"ABCDE"但是"AEC"不是）
例如：
S=“nowcccoder”, T = “nowccoder”
回傳3

狀態定義怎么寫，其實和上題類似，我們的變數只給一個的話，是不好往后面推導的，所以我們這邊用F（i，j）表示前S的前i個字符和T的前j個字符的不同子序列個數

狀態轉換，解決這個就基本解決這道題了，我們怎么思考這個問題呢，看S=“nowcccoder”, T = “nowccoder”，的這組測驗用例，其實很難說一下子就有思路，我們畫個二維圖幫助大家理解，

二維圖我們S=“nowccc”, T = “nowcc”，方便大家理解

重點觀察 （6，4）這個位置
情況一：當第i個字符和第j個字符相同時，可以看出（6，4）位置的組成其實就是（5，5）+（5，4）組成的，為什么是這樣，其實F（i，j） 就是考慮第i個元素是否需要，不需要為一種情況，需要為一種情況，其中（5，5）對應不需要第i個元素，而（5，4）對應需要第i個元素
所以我們的轉換方程出來了：F（i，j）=F（i-1，j-1）+F（i，j-1）
情況二：當第i個字符和第j個字符不相同時
即 F（i，j）=F（i，j-1），即我們的(5,4)的第i個元素和第j個元素若不想等則與他無關

再給一個位置的資料驗證

同理我們可以看出 （5，4）位置也是如此，（5，3）這個位置為什么不使用？ - - 其實是因為如果我們不清楚 i ==5的時候第五個字符是否有被使用到，當然我們給的測驗用例是沒有使用到第五個字符的，所以我們不可以使用這個位置，因為只有確保使用到當前i個字符我們才好推導下一個狀態，類似我們上一章講到的最大連續子陣列和(Maximum Subarray)

初始化：看到大家肯定都熟能生巧了，我們剛剛所F（i，j）用到了F（i-1，j）和F(i-1 ,j-1),所以我們給一個二維陣列的時候多給多一行一列，
初始化的內容**F（i，0）**表示從i個字符的找到子序列和空串相同，
第一種解釋：空集是所有集的子集，所以我們F（i，0）全部置成1，
第二種解釋，當我們的元素一開始不相等，直到S第i個元素，才和T的第一個元素相等的時候，我們需要一個空串作為輔助狀態，如下圖，圖中有解釋
到F（0，j）就好解決了，我們的S為空字串就沒有什么子序列了，所以F（0，j） 全部置成0

總結

講到這里，我們的動規也就告一段落了，之后我會發布繼續更新演算法，下節的演算法會給大家帶來搜索，廣度遍歷搜索和深度遍歷搜索，
制作不易，一鍵三連！！！！！！！！