Algorithm-week8

Week8

Program--Medium--712.Minimum ASCII Delete Sum for Two Strings

Given two strings 

s1, s2

, find the lowest ASCII sum of deleted characters to make two strings equal.

Example 1:

Input: s1 = "sea", s2 = "eat"
Output: 231
Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum.
Deleting "t" from "eat" adds 116 to the sum.
At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.
      

Example 2:

Input: s1 = "delete", s2 = "leet"
Output: 403
Explanation: Deleting "dee" from "delete" to turn the string into "let",
adds 100[d]+101[e]+101[e] to the sum.  Deleting "e" from "leet" adds 101[e] to the sum.
At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403.
If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.
      

Note:

• 0 < s1.length, s2.length <= 1000

  .
• All elements of each string will have an ASCII value in 

  [97, 122]

  .

  題目解析：

  這是一道标準的動态規劃的題目，動态規劃的題目的重點是狀态的确定以及狀态之間的轉移關系。對于最少多少枚不同面值硬币能組成一定金額的錢的問題，它的狀态就是組成金額n前的n-1個狀态，即組成金額為1,2,3....等。通過求解前幾個狀态的最小值，從中選擇最小的加1，我們就能夠求解狀态n的最小值。是以動态規劃似乎也有分治的思想在裡面，但是這裡的子問題間是互相影響的，不能單純由子問題拼接而成，隻能一步一步由簡單狀态向複雜狀态轉化。

  這個問題也是類似的，整個問題可劃分為不同狀态子問題求解的最優轉化，求兩段長的字元串求最小删除字元和以緻兩段字元串相同，可以分解為兩段更小的字元串求相同問題，不過比原問題少一兩個字元。對于長度分别為(m, n)的字元串，隻要我們求得(m-1, n)或者(m, n-1)長字元串的問題求解，在從中選擇最小值作為原問題的上一個狀态值即可。下面是算法的基本流程：

  1.初始化起始基本狀态，即長度為0與第二個字元串不同長度間最小删除得出相同字元串就是将所有字元都删除。

  2.進行狀态轉移，對于字元串1中不同長度的子串，與字元傳2的不同長度的子串找最小删除字元和。

  3.在一個字元串增長時，假設增加的字元與另一個字元串尾字元相同，則找到相同字元串中的一個字元，這時候不用删除，代價等于上一個狀态。

  4.在一個字元串增長時，假設增加的字元與另一個字元串尾不同，則需要删除一個字元。假設目前狀态為長度[m, n]，則前一個狀态可能為[m-1, n]和[m, n-1]，那麼，我們就從中選取最小的，保持前面字元串求解中找到的最多相同的狀态，因為兩個字元串中相同的越多，那麼删除的就越小。

  代碼：

  class Solution {
  public:
      int minimumDeleteSum(string s1, string s2) {
          int m = s1.length();
          int n = s2.length();
          vector<vector<int>> cost(m + 1, vector<int>(n + 1, 0));
          cost[0][0] = 0;
          for (int j = 1; j < n + 1; j++) {
              cost[0][j] = cost[0][j - 1] + s2[j - 1];
          }
          
          for (int i = 1; i < m + 1; i++) {
              cost[i][0] = cost[i - 1][0] + s1[i - 1];
              for (int j = 1; j < n + 1; j++) {
                  if (s1[i - 1] == s2[j - 1]) {
                      cost[i][j] = cost[i - 1][j - 1];
                  } else {
                      cost[i][j] = min(cost[i - 1][j] + s1[i - 1], cost[i][j - 1] + s2[j - 1]);
                  }
              }
          }
          return cost[m][n];
      }
  };