代碼隨想錄算法訓練營29期|day59 任務以及具體安排

第九章?動態規劃part16

  • ?583.?兩個字符串的刪除操作?
    // dp數組中存儲word1和word2最長相同子序列的長度
class Solution {public int minDistance(String word1, String word2) {int len1 = word1.length();int len2 = word2.length();int[][] dp = new int[len1 + 1][len2 + 1];for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; j++) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return len1 + len2 - dp[len1][len2] * 2;}
}// dp數組中存儲需要刪除的字符個數
class Solution {public int minDistance(String word1, String word2) {int[][] dp = new int[word1.length() + 1][word2.length() + 1];for (int i = 0; i < word1.length() + 1; i++) dp[i][0] = i;for (int j = 0; j < word2.length() + 1; j++) dp[0][j] = j;for (int i = 1; i < word1.length() + 1; i++) {for (int j = 1; j < word2.length() + 1; j++) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];}else{dp[i][j] = Math.min(dp[i - 1][j - 1] + 2,Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));}}}return dp[word1.length()][word2.length()];}
}

    思路：dp數組表示需要刪除的字符的最小個數，遞推公式如果word1[i-1]和word2[j-1]相等的話，直接將dp[i-1][j-1]賦值給dp[i][j]，如果不相等的話，就比較取最小值。還有一個關鍵的地方在于初始化dp數組，當i=0時表示word1為null需要將word2里面的字符全部刪掉。j=0時同理。

  • ?72.?編輯距離?
    public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();int[][] dp = new int[m + 1][n + 1];// 初始化for (int i = 1; i <= m; i++) {dp[i][0] =  i;}for (int j = 1; j <= n; j++) {dp[0][j] = j;}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {// 因為dp數組有效位從1開始// 所以當前遍歷到的字符串的位置為i-1 | j-1if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;}}}return dp[m][n];
}

    思路：關鍵就是推導遞推公式，dp數組表示i-1變為j-1所需的最小操作數。

    2. 確定遞推公式

    在確定遞推公式的時候，首先要考慮清楚編輯的幾種操作，整理如下：

    if (word1[i - 1] == word2[j - 1])不操作
if (word1[i - 1] != word2[j - 1])增刪換

    也就是如上4種情況。

    if (word1[i - 1] == word2[j - 1])?那么說明不用任何編輯，dp[i][j]?就應該是?dp[i - 1][j - 1]，即dp[i][j] = dp[i - 1][j - 1];

    此時可能有同學有點不明白，為啥要即dp[i][j] = dp[i - 1][j - 1]呢？

    那么就在回顧上面講過的dp[i][j]的定義，word1[i - 1]?與?word2[j - 1]相等了，那么就不用編輯了，以下標i-2為結尾的字符串word1和以下標j-2為結尾的字符串word2的最近編輯距離dp[i - 1][j - 1]就是?dp[i][j]了。

    在下面的講解中，如果哪里看不懂，就回想一下dp[i][j]的定義，就明白了。

    在整個動規的過程中，最為關鍵就是正確理解dp[i][j]的定義！

    if (word1[i - 1] != word2[j - 1])，此時就需要編輯了，如何編輯呢？

  • 操作一：word1刪除一個元素，那么就是以下標i - 2為結尾的word1 與 j-1為結尾的word2的最近編輯距離 再加上一個操作。

  • 即?dp[i][j] = dp[i - 1][j] + 1;

  • 操作二：word2刪除一個元素，那么就是以下標i - 1為結尾的word1 與 j-2為結尾的word2的最近編輯距離 再加上一個操作。

  • 即?dp[i][j] = dp[i][j - 1] + 1;

    這里有同學發現了，怎么都是刪除元素，添加元素去哪了。

    word2添加一個元素，相當于word1刪除一個元素，例如?word1 = "ad" ，word2 = "a"，word1刪除元素'd'?和?word2添加一個元素'd'，變成word1="a", word2="ad"， 最終的操作數是一樣！ dp數組如下圖所示意的：

                a                         a     d+-----+-----+             +-----+-----+-----+|  0  |  1  |             |  0  |  1  |  2  |+-----+-----+   ===>      +-----+-----+-----+a |  1  |  0  |           a |  1  |  0  |  1  |+-----+-----+             +-----+-----+-----+d |  2  |  1  |+-----+-----+

    操作三：替換元素，word1替換word1[i - 1]，使其與word2[j - 1]相同，此時不用增刪加元素。

    可以回顧一下，if (word1[i - 1] == word2[j - 1])的時候我們的操作 是?dp[i][j] = dp[i - 1][j - 1]?對吧。

    那么只需要一次替換的操作，就可以讓 word1[i - 1] 和 word2[j - 1] 相同。

    所以?dp[i][j] = dp[i - 1][j - 1] + 1;

    綜上，當?if (word1[i - 1] != word2[j - 1])?時取最小的，即：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

    遞歸公式代碼如下：

    if (word1[i - 1] == word2[j - 1]) {dp[i][j] = dp[i - 1][j - 1];
}
else {dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
}
  • ?編輯距離總結篇???

    動態規劃之編輯距離總結篇

    本周我們講了動態規劃之終極絕殺：編輯距離，為什么叫做終極絕殺呢？

    細心的錄友應該知道，我們在前三篇動態規劃的文章就一直為 編輯距離 這道題目做鋪墊。

    #判斷子序列

    動態規劃：392.判斷子序列?(opens new window)給定字符串 s 和 t ，判斷 s 是否為 t 的子序列。

    這道題目 其實是可以用雙指針或者貪心的的，但是我在開篇的時候就說了這是編輯距離的入門題目，因為從題意中我們也可以發現，只需要計算刪除的情況，不用考慮增加和替換的情況。

  • if (s[i - 1] == t[j - 1])
    • t中找到了一個字符在s中也出現了
  • if (s[i - 1] != t[j - 1])
    • 相當于t要刪除元素，繼續匹配

  • 狀態轉移方程：

    if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = dp[i][j - 1];

    #不同的子序列

    動態規劃：115.不同的子序列?(opens new window)給定一個字符串 s 和一個字符串 t ，計算在 s 的子序列中 t 出現的個數。

    本題雖然也只有刪除操作，不用考慮替換增加之類的，但相對于動態規劃：392.判斷子序列?(opens new window)就有難度了，這道題目雙指針法可就做不了。

    當s[i - 1] 與 t[j - 1]相等時，dp[i][j]可以有兩部分組成。

    一部分是用s[i - 1]來匹配，那么個數為dp[i - 1][j - 1]。

    一部分是不用s[i - 1]來匹配，個數為dp[i - 1][j]。

    這里可能有同學不明白了，為什么還要考慮 不用s[i - 1]來匹配，都相同了指定要匹配啊。

    例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]來匹配，即用s[0]s[1]s[2]組成的bag。

    當然也可以用s[3]來匹配，即：s[0]s[1]s[3]組成的bag。

    所以當s[i - 1] 與 t[j - 1]相等時，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

    當s[i - 1] 與 t[j - 1]不相等時，dp[i][j]只有一部分組成，不用s[i - 1]來匹配，即：dp[i - 1][j]

    所以遞推公式為：dp[i][j] = dp[i - 1][j];

    狀態轉移方程：

    if (s[i - 1] == t[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {dp[i][j] = dp[i - 1][j];
}

    #兩個字符串的刪除操作

    動態規劃：583.兩個字符串的刪除操作?(opens new window)給定兩個單詞 word1 和 word2，找到使得 word1 和 word2 相同所需的最少步數，每步可以刪除任意一個字符串中的一個字符。

    本題和動態規劃：115.不同的子序列?(opens new window)相比，其實就是兩個字符串可以都可以刪除了，情況雖說復雜一些，但整體思路是不變的。

  • 當word1[i - 1] 與 word2[j - 1]相同的時候
  • 當word1[i - 1] 與 word2[j - 1]不相同的時候

  • 當word1[i - 1] 與 word2[j - 1]相同的時候，dp[i][j] = dp[i - 1][j - 1];

    當word1[i - 1] 與 word2[j - 1]不相同的時候，有三種情況：

    情況一：刪word1[i - 1]，最少操作次數為dp[i - 1][j] + 1

    情況二：刪word2[j - 1]，最少操作次數為dp[i][j - 1] + 1

    情況三：同時刪word1[i - 1]和word2[j - 1]，操作的最少次數為dp[i - 1][j - 1] + 2

    那最后當然是取最小值，所以當word1[i - 1] 與 word2[j - 1]不相同的時候，遞推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

    狀態轉移方程：

    if (word1[i - 1] == word2[j - 1]) {dp[i][j] = dp[i - 1][j - 1];
} else {dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});
}

    #編輯距離

    動態規劃：72.編輯距離?(opens new window)給你兩個單詞 word1 和 word2，請你計算出將 word1 轉換成 word2 所使用的最少操作數 。

    編輯距離終于來了，有了前面三道題目的鋪墊，應該有思路了，本題是兩個字符串可以增刪改，比?動態規劃：判斷子序列?(opens new window)，動態規劃：不同的子序列?(opens new window)，動態規劃：兩個字符串的刪除操作?(opens new window)都要復雜的多。

    在確定遞推公式的時候，首先要考慮清楚編輯的幾種操作，整理如下：

  • if (word1[i - 1] == word2[j - 1])
    • 不操作
  • if (word1[i - 1] != word2[j - 1])
    • 增
    • 刪
    • 換

  • 也就是如上四種情況。

    if (word1[i - 1] == word2[j - 1]) 那么說明不用任何編輯，dp[i][j] 就應該是 dp[i - 1][j - 1]，即dp[i][j] = dp[i - 1][j - 1];

    此時可能有同學有點不明白，為啥要即dp[i][j] = dp[i - 1][j - 1]呢？

    那么就在回顧上面講過的dp[i][j]的定義，word1[i - 1] 與 word2[j - 1]相等了，那么就不用編輯了，以下標i-2為結尾的字符串word1和以下標j-2為結尾的字符串word2的最近編輯距離dp[i - 1][j - 1] 就是 dp[i][j]了。

    在下面的講解中，如果哪里看不懂，就回想一下dp[i][j]的定義，就明白了。

    在整個動規的過程中，最為關鍵就是正確理解dp[i][j]的定義！

    if (word1[i - 1] != word2[j - 1])，此時就需要編輯了，如何編輯呢？

    操作一：word1增加一個元素，使其word1[i - 1]與word2[j - 1]相同，那么就是以下標i-2為結尾的word1 與 i-1為結尾的word2的最近編輯距離 加上一個增加元素的操作。

    即 dp[i][j] = dp[i - 1][j] + 1;

    操作二：word2添加一個元素，使其word1[i - 1]與word2[j - 1]相同，那么就是以下標i-1為結尾的word1 與 j-2為結尾的word2的最近編輯距離 加上一個增加元素的操作。

    即 dp[i][j] = dp[i][j - 1] + 1;

    這里有同學發現了，怎么都是添加元素，刪除元素去哪了。

    word2添加一個元素，相當于word1刪除一個元素，例如 word1 = "ad" ，word2 = "a"，word2添加一個元素d，也就是相當于word1刪除一個元素d，操作數是一樣！

    操作三：替換元素，word1替換word1[i - 1]，使其與word2[j - 1]相同，此時不用增加元素，那么以下標i-2為結尾的word1 與 j-2為結尾的word2的最近編輯距離 加上一個替換元素的操作。

    即 dp[i][j] = dp[i - 1][j - 1] + 1;

    綜上，當 if (word1[i - 1] != word2[j - 1]) 時取最小的，即：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

    遞歸公式代碼如下：

    if (word1[i - 1] == word2[j - 1]) {dp[i][j] = dp[i - 1][j - 1];
}
else {dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
}

    #總結

    心思的錄友應該會發現我用了三道題做鋪墊，才最后引出了動態規劃：72.編輯距離?(opens new window)，Carl的良苦用心呀，你們體會到了嘛！

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/697602.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/697602.shtml
英文地址，請注明出處：http://en.pswp.cn/news/697602.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

Gartner信息圖：2024 年44種安全和風險管理技術采用路線圖

Gartner信息圖：2024 年44種安全和風險管理技術采用路線圖

Gartner發布的該信息圖確定了全球企業正在采用的 44 種安全相關技術&#xff0c;并根據采用階段、部署風險和企業價值對它們進行了映射。安全和風險管理領導者可以使用此信息圖將他們的技術投資與同行進行比較。 2024 年安全和風險管理技術采用路線圖 SRM 領導者可以使用此信息…
閱讀更多...
世微AP8P059 靜態功耗小 太陽能人體紅外線感應IC

世微AP8P059 靜態功耗小 太陽能人體紅外線感應IC

概述 AP8P059 是一款集成低壓 LDO 、光 控、充電控制、過充保護、欠壓保護、 PIR 感應、延時為一體的人體感應太陽能 LED 燈控制芯片&#xff0c;只需要很少的外接元件&#xff0c;適 用于鋰電池供電的 PIR 人體感應 LED 燈具 的應用。 外置的一級帶通增益放大 器便…
閱讀更多...
Python實現視頻轉音頻、音頻轉文本的最佳方法

Python實現視頻轉音頻、音頻轉文本的最佳方法

文章目錄 Python實現視頻轉音頻和音頻轉文字視頻轉音頻步驟 1&#xff1a;導入moviepy庫步驟 2&#xff1a;選擇視頻文件步驟 3&#xff1a;創建VideoFileClip對象步驟 4&#xff1a;提取音頻步驟 5&#xff1a;保存音頻文件 音頻轉文字步驟 1&#xff1a;導入SpeechRecognitio…
閱讀更多...
RV新聞概要 --- 2024/02/23

RV新聞概要 --- 2024/02/23

來源&#xff1a;https://mp.weixin.qq.com/s/EEJVLQnXvgQTbtU_yrW9lw 晶心科技是一家上市公司&#xff08;TWSE&#xff1a;6533&#xff1b;SIN&#xff1a;US03420C2089&#xff1b;ISIN&#xff1a;US03420C1099&#xff09;&#xff0c;已有18 年的經營歷史&#xff0c;是…
閱讀更多...
單向循環鏈表的操作

單向循環鏈表的操作

main函數&#xff1a; #ifndef __loopLinkList_H__#define __loopLinkList_H__typedef int datatype;union msg{ //若數據的類型也為int&#xff0c;則不需要這個聯合體datatype data;int len; //放頭結點&#xff0c;記錄鏈表長度};typedef struct node{union msg te…
閱讀更多...
Istio實戰：Istio Kiali部署與驗證

Istio實戰：Istio Kiali部署與驗證

目錄 前言一、Istio安裝小插曲 注意事項 二、Kiali安裝三、Istio測試參考資料 前言 前幾天我就開始搗騰Istio。前幾天在執行istioctl install --set profiledemo -y 的時候老是在第二步就報錯了&#xff0c;開始我用的istio版本是1.6.8。 后面查看k8s與istio的版本對應關系后發…
閱讀更多...
vCenter、vSphere Client硬盤擴容詳解

vCenter、vSphere Client硬盤擴容詳解

文章目錄 1、需求2、vSphere 操作流程3、服務器操作3.1、查看分區空間大小3.2、列出所有可用塊設備的信息3.3、新建分區3.4、重讀分區表信息3.5、格式化分區信息3.6、查看卷組的詳細狀態3.7、創建物理卷3.8、擴容卷組3.9、邏輯卷在線擴容3.10、顯示物理卷屬性3.11、XFS 文件系統…
閱讀更多...
最少停車數（C 語言）

最少停車數（C 語言）

題目描述 特定大小的停車場&#xff0c;數組cars[]表示&#xff0c;其中1表示有車&#xff0c;0表示沒車。車輛大小不一&#xff0c;小車占一個車位&#xff08;長度1&#xff09;&#xff0c;貨車占兩個車位&#xff08;長度2&#xff09;&#xff0c;卡車占三個車位&#xf…
閱讀更多...
Rollup + Ts

Rollup + Ts

Rollup Ts RollupTs demo 一、文件配置 | - src | | - utils | | | - .ts | | - .babelrc | | - main.js | | - style.css | - package.json | - rollup.config.js | - tsconfig.json二、插件下載 rollup // rollup 基本的包 typescript // ts 包 rollup/plug…
閱讀更多...
如何做bug分析 ？bug分析什么 ？ 為什么要做bug分析 ？

如何做bug分析 ？bug分析什么 ？ 為什么要做bug分析 ？

每當我們完成一個版本測試時&#xff0c;總會在測試報告中添加一些分析bug的指標 &#xff0c;主要用于分析在測試過程中存在的問題 。但是在分析的過程中你就可能遇到如下的問題 &#xff1a; 我應該分析那些指標呢 &#xff1f;每一個具體的指標該如何分析 &#xff1f;它能說…
閱讀更多...
Vue3學習——computed、watch、watchEffect

Vue3學習——computed、watch、watchEffect

computed 與Vue2.x中computed配置功能一致寫法 import {computed} from vuesetup(){...//計算屬性——簡寫let fullName computed(()>{return person.firstName - person.lastName})//計算屬性——完整let fullName computed({get()return person.firstName - perso…
閱讀更多...
算法——模擬

算法——模擬

1. 什么是模擬算法&#xff1f; 官方一點來說 模擬算法&#xff08;Simulation Algorithm&#xff09;是一種通過模擬現實或抽象系統的運行過程來研究、分析或解決問題的方法。它通常涉及創建一個模型&#xff0c;模擬系統中的各種事件和過程&#xff0c;以便觀察系統的行為&a…
閱讀更多...
Redis緩存一致性問題(自用記錄)

Redis緩存一致性問題(自用記錄)

背景 在開發過程中&#xff0c;redis緩存技術被大范圍應用。由于現在的系統大多是分布式的&#xff0c;高并發的&#xff0c;redis和傳統的數據庫&#xff0c;存在數據不一致的問題。 解決方案 本文主要探討兩者數據不一致的解決方案&#xff1a; 給緩存設置過期時間&#x…
閱讀更多...
dell戴爾電腦靈越系列Inspiron 15 3520原廠Win11系統中文版/英文版

dell戴爾電腦靈越系列Inspiron 15 3520原廠Win11系統中文版/英文版

Dell戴爾筆記本靈越3520原裝出廠Windows11系統包&#xff0c;恢復出廠開箱預裝OEM系統 鏈接&#xff1a;https://pan.baidu.com/s/1mMOAnvXz5NCDO_KImHR5gQ?pwd3nvw 提取碼&#xff1a;3nvw 原廠系統自帶所有驅動、出廠主題壁紙、系統屬性聯機支持標志、Office辦公軟件、MyD…
閱讀更多...
Jmeter接口測試 ，這應該是全網最詳細的教程了

Jmeter接口測試 ，這應該是全網最詳細的教程了

&#x1f345; 視頻學習&#xff1a;文末有免費的配套視頻可觀看 &#x1f345; 關注公眾號【互聯網雜貨鋪】&#xff0c;回復 1 &#xff0c;免費獲取軟件測試全套資料&#xff0c;資料在手&#xff0c;漲薪更快 一、Jmeter 的使用步驟 打開Jmeter 安裝包&#xff0c;進入\bi…
閱讀更多...
postman-使用Postman的模擬服務來模擬（mock）后端數據，完成前端模擬API調用

postman-使用Postman的模擬服務來模擬（mock）后端數據，完成前端模擬API調用

最近項目上比較忙&#xff0c;任務多時間緊&#xff0c;導致后端開發任務繁多&#xff0c;無法及時開發完畢&#xff0c;但是前端同學已經把對應功能開發完成&#xff0c;需要進行前后端聯調來驗證API及一些交互問題&#xff1b;這不能因為后端的進度來影響前端的工作完成情況&…
閱讀更多...
【Linux進程】馮·諾依曼體系結構以及操作系統的深入理解

【Linux進程】馮·諾依曼體系結構以及操作系統的深入理解

&#x1f4d9; 作者簡介 &#xff1a;RO-BERRY &#x1f4d7; 學習方向&#xff1a;致力于C、C、數據結構、TCP/IP、數據庫等等一系列知識 &#x1f4d2; 日后方向 : 偏向于CPP開發以及大數據方向&#xff0c;歡迎各位關注&#xff0c;謝謝各位的支持 目錄 1.馮諾依曼體系結構特…
閱讀更多...
kafka和ZK的關系

kafka和ZK的關系

zk相當于是kafka的一個基礎設施 Kafka是一種高吞吐量、可擴展的分布式發布訂閱消息系統&#xff0c;ZooKeeper是一個分布式協調服務&#xff0c;用于管理和協調分布式系統中的各種資源 Zookeeper&#xff1a;管理broker&#xff0c;consumer 創建broker后&#xff0c;向zk注冊…
閱讀更多...
適用于生物行業的樣本管理系統

適用于生物行業的樣本管理系統

在生物樣本管理系統的應用中&#xff0c;我們首先需要了解生物樣本的特點和要求。生物樣本具有多樣性和易變性&#xff0c;需要被妥善保存和跟蹤&#xff0c;以確保其質量和可用性。 因此&#xff0c;一個有效的生物樣本管理系統需要具備以下特點&#xff1a; 全面性&#xff1…
閱讀更多...
Spring Event的原理以及缺陷

Spring Event的原理以及缺陷

原理:Spring 事件監聽機制及原理分析 - Admol - 博客園 (cnblogs.com) 使用bug:Spring Event 別瞎用&#xff01;從我司的悲劇中&#xff0c;我總結了6 條最佳實踐&#xff01;-騰訊云開發者社區-騰訊云 (tencent.com)
閱讀更多...
最新文章

Copyright @ 2022~2023