『嗨威說』演算法設計與分析 - PTA 數字三角形 / 最大子段和 / 編輯距離問題（第三章上機實踐報告）

• 2019 年 10 月 19 日
• 筆記

本文索引目錄：

一、PTA實驗報告題1 ： 數字三角形

　　1.1　　實踐題目

　　1.2　　問題描述

　　1.3　　演算法描述

　　1.4　　演算法時間及空間複雜度分析

二、PTA實驗報告題2 ： 最大子段和

　　2.1　　實踐題目

　　2.2　　問題描述

　　2.3　　演算法描述

　　2.4　　演算法時間及空間複雜度分析

三、PTA實驗報告題3 ： 編輯距離問題

　　3.1　　實踐題目

　　3.2　　問題描述

　　3.3　　演算法描述

　　3.4　　演算法時間及空間複雜度分析

四、實驗心得體會（實踐收穫及疑惑）

一、PTA實驗報告題1 ： 數字三角形

　　1.1　　實踐題目：

　　1.2　　問題描述：

　　　　　題意是，題干給你一個三角形（實際上就是半個矩形即下三角形模式或上三角形模式），要求你從頂部計算出到底部最佳的路線，使得經過的數字總和最大。

　　1.3　　演算法描述：

這道題很明顯需要用到動態規劃的方法，存在重疊子問題，因此我們需要找出這道題的動態轉移方程。

我們通過模擬可以發現，樣例最佳的行走路徑是：

 很明顯發現，我們並不能通過貪心演算法來做這道題，只能用動態規劃找出最佳路徑。

首先我們需要建立dp數組，定義dp數組的含義為：截至當前位置已走過的數的總和，我們先初始化dp數組。

要確認當前位置，也就需要定義成二維數組，第一個指定為行，第二個指定為具體列。

 第二步，我們需要確定動態方程，很明顯我們知道：

方程為：dp[i][j] = temp[i][j] + max(dp[i+1][j],dp[i+1][j+1])

以最後兩列為例，模擬動規過程：

 可以很明顯的發現，當下面兩格相比，取出最大值，加上自己本身，就是當前的dp值，依照這個思路

我們可以把整個dp過程模擬完成：

到此模擬完成，我們可以很清楚的看到，我們最終想要的答案，就在最頂層，dp[1][1]中，我們只需要固定輸出這個值即可得到答案。

第三步，確認我們的填表順序，從以上的分析角度可以知道，dp方程中當前dp依賴於當前位置的下一行同列以及下一行同列+1的位置，所以需要從下往上填表，分析完畢，按著這個思路敲出程式碼即可，

完整程式碼展示如下：

#include<bits/stdc++.h>  using namespace std;  int n,temp[105][105],ans = 0;  int main()  {      /* input */      cin>>n;      for(int i = 1;i<=n;i++)          for(int j = 1;j<=i;j++)              cin>>temp[i][j];        /* 動規轉移方程： dp[i][j] = temp[i][j] + max(dp[i+1][j],dp[i+1][j+1]);*/        /* down to up */      for(int i = n;i>0;i--)          for(int j = 1;j<=i;j++)              temp[i][j] = temp[i][j] + max(temp[i+1][j],temp[i+1][j+1]);        /* answer */      cout<<temp[1][1];   } 

　　1.4　　演算法時間及空間複雜度分析：

　　　整體演算法上看，動態規劃是不計算重複子問題，並優化計算過程，防止計算重複，經過分析可知，我們需要O（n^2）時間初始化dp數組，需要O（1/2 * n^2）的時間進行填表，最後輸出，總的來看時間複雜度為O（n^2）。

　　　動態規劃需要用到輔助空間二維數組進行填表，表的大小根據問題規模確定，因此空間複雜度是O（n^2）。

二、PTA實驗報告題2 ： 最大子段和

　　2.1　　實踐題目：

　　2.2　　問題描述：

　　　　第二題是動態規劃的小小壓縮版本，題意是說給一段序列，求怎麼取一小段，使得加和數最大，也即最大子段和問題。

　　2.3　　演算法描述：

　　　　首先，分析題目選擇相應演算法，雖然這章都是在學動態規劃，但是在平時拿到題目的時候，我們是不知道這是動態規劃的，所以需要分析問題，一般這種求最值問題，常常先考慮貪心能否使用，可以發現這道題是可以使用貪心演算法的，所以我也使用貪心演算法寫了一次，但是呢鑒於題目要求需要O（n）的時間複雜度，因此優先考慮動態規劃啦。

 　　　  第二，初始化dp數組，定義dp數組dp[i]為從1到i中最大的子段和。

 　　　   第三，動態規劃轉移方程，明顯可以知道：dp[ i ] = max( dp[ i-1 ] , k ) ; k 為從0-i的加和大於0的子段，一旦小於0就從當前位置重新計段長。

　　　　模擬過程如下：

 　　因此我們就可以很愉快的寫出程式碼啦。AC程式碼如下：

#include<bits/stdc++.h>  using namespace std;  int n,temp[10005],dp[10005],flag = 0,k;  int main()  {      /* input */      cin>>n;      for(int i = 1;i<=n;i++)      {          cin>>temp[i];          if(temp[i] >=0) flag = 1;      }        /*    dp[i]:1-i中最大子段和          k: k從0到i加和大於0的子段，遇到子段小於0的扔掉重新開始計長度*/      for(int i = 1;i<=n;i++)      {          if(k>0) k += temp[i];          else k=temp[i];          dp[i] = max(dp[i-1], k);      }        /* answer */      if(flag == 0) cout<<0;      else cout<<dp[n];      return 0;  }

　　2.4　　演算法時間及空間複雜度分析：

　　　　演算法複雜度跟題目要求一致，時間複雜度為O(n)。

　　　　空間複雜度需要一個一維數組dp，因此空間複雜度也是O（n）

三、PTA實驗報告題3 ： 編輯距離問題

　　3.1　　實踐題目：

　　3.2　　問題描述：

　　　　該題目為：題目意思是給定兩端英文序列，要求將A序列變成B序列，可以通過對A進行刪除、插入、更換任意字元，得到B序列，要求以最少步驟為準。

　　3.3　　演算法描述：

　　　　這道題我和三木在寫的時候第一次沒有寫出來，三木想到一個絕佳的數學公式，用最大長度字元串長減去LCS即為所求，但是答案WA在了第三點，後來發現存在特例無法解決，所以課後我又換了一種方式，這裡我講解的還不是很好，在一個部落格我看到一個非常完整很棒的講解，貼出來給大家看看吧：

　　https://blog.csdn.net/weixin_42681158/article/details/89411572

　　我的AC程式碼如下：

#include<bits/stdc++.h>  using namespace std;  int dp[2005][2005];  char a[2005];  char b[2005];  int minval(int a,int b,int c){      int temp = max(a,b);      return max(temp,c);  }  int LCS(char *a,char *b)  {      memset(dp,0,sizeof(dp));      int lena=strlen(a);      int lenb=strlen(b);      for(int i=1;i<=lena;i++)      {          for(int j=1;j<=lenb;j++)          {              if(a[i-1]==b[j-1])                  dp[i][j]=minval(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+1);              else                  dp[i][j]=minval(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]);          }      }      return dp[lena][lenb];  }    int main()  {      cin>>a;      getchar();      cin>>b;      int maxss =max(strlen(a),strlen(b));          cout<<maxss-LCS(a,b);        return 0;  }

　　3.4　　演算法時間及空間複雜度分析：

　　　　由分析易知，時間複雜度和空間複雜度均為O（n^2）

四、實驗心得體會（實踐收穫及疑惑）：

　　經過第一次實踐合作之後，第二次的實踐合作愈發順利，雖然第三題有一小點WA了，不過還是很合作默契的哈哈。（主要是三木太強了）

簡單通過書本和部落格總結了一下動態規劃的一些基本特點如下：

 ===動態規劃問題的特點：

（1）最優化原理：如果問題的最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構，即滿足最優化原理。

（2）重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。（該性質並不是動態規劃適用的必要條件，但是如果沒有這條性質，動態規劃演算法同其他演算法相比就不具備優勢）

===動規解題的一般思路：

　　動態規劃所處理的問題是一個多階段決策問題，一般由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優的活動路線)。

　　動態規劃的設計都有著一定的模式，一般要經歷以下幾個步驟。

　　　　初始狀態→│決策１│→│決策２│→…→│決策ｎ│→結束狀態

　 （1）劃分階段：按照問題的時間或空間特徵，把問題分為若干個階段。在劃分階段時，注意劃分後的階段一定要是有序的或者是可排序的，否則問題就無法求解。    

　 （2）確定狀態和狀態變數：將問題發展到各個階段時所處於的各種客觀情況用不同的狀態表示出來。當然，狀態的選擇要滿足無後效性。    

　 （3）確定決策並寫出狀態轉移方程：因為決策和狀態轉移有著天然的聯繫，狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態。所以如果確定了決策，狀態轉移方程也就可寫出。但事實上常常是反過來做，根據相鄰兩個階段的狀態之間的關係來確定決策方法和狀態轉移方程。    

　 （4）尋找邊界條件：給出的狀態轉移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。

如有錯誤不當之處，煩請指正。