規(guī)劃-5】72.編輯距離)
題目描述給你兩個單詞word1和word2請返回將word1轉(zhuǎn)換成word2所使用的最少操作數(shù)。你可以對一個單詞進行如下三種操作插入一個字符刪除一個字符替換一個字符示例 1輸入word1 horse, word2 ros輸出3解釋horse - rorse (將 h 替換為 r) rorse - rose (刪除 r) rose - ros (刪除 e)示例 2輸入word1 intention, word2 execution輸出5解釋intention - inention (刪除 t) inention - enention (將 i 替換為 e) enention - exention (將 n 替換為 x) exention - exection (將 n 替換為 c) exection - execution (插入 u)解題思路方法一動態(tài)規(guī)劃核心思路狀態(tài)定義dp[i][j] 將word1的前i個字符轉(zhuǎn)換成word2的前j個字符所需的最少操作數(shù)。狀態(tài)轉(zhuǎn)移對于word1[i-1]和word2[j-1]情況1字符相同dp[i][j] dp[i-1][j-1] 不需要操作情況2字符不同dp[i][j] 1 min( dp[i-1][j], // 刪除 word1[i-1] dp[i][j-1], // 插入 word2[j-1] dp[i-1][j-1] // 替換 word1[i-1] 為 word2[j-1] )初始化dp[0][j] jword1 為空需要插入 j 個字符dp[i][0] iword2 為空需要刪除 i 個字符具體過程示例word1 horse, word2 rosdp: r o s 0 1 2 3 h 1 1 2 3 o 2 2 1 2 r 3 2 2 2 s 4 3 3 2 e 5 4 4 3 dp[5][3] 3 ?代碼實現(xiàn)寫法1二維 DPclass Solution { public: int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorvectorint dp(m 1, vectorint(n 1, 0)); // 初始化 for (int i 0; i m; i) dp[i][0] i; for (int j 0; j n; j) dp[0][j] j; // 狀態(tài)轉(zhuǎn)移 for (int i 1; i m; i) { for (int j 1; j n; j) { if (word1[i-1] word2[j-1]) { dp[i][j] dp[i-1][j-1]; } else { dp[i][j] 1 min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}); } } } return dp[m][n]; } };寫法2一維 DP空間優(yōu)化class Solution { public: int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorint dp(n 1, 0); // 初始化word1 為空 for (int j 0; j n; j) dp[j] j; for (int i 1; i m; i) { int prev dp[0]; // 保存 dp[i-1][j-1] dp[0] i; // dp[i][0] i for (int j 1; j n; j) { int temp dp[j]; // 保存 dp[i-1][j] if (word1[i-1] word2[j-1]) { dp[j] prev; } else { dp[j] 1 min({dp[j], dp[j-1], prev}); } prev temp; // 更新 prev } } return dp[n]; } };復雜度分析方法時間復雜度空間復雜度二維 DPO(m × n)O(m × n)一維 DPO(m × n)O(n)關鍵細節(jié)1. 三種操作對應哪些狀態(tài)操作狀態(tài)轉(zhuǎn)移含義刪除dp[i-1][j]刪除 word1[i-1] 后用前 i-1 個字符匹配 j 個插入dp[i][j-1]插入 word2[j-1] 后用 i 個字符匹配前 j-1 個替換dp[i-1][j-1]替換 word1[i-1] 為 word2[j-1] 后匹配前 i-1 和前 j-12. 為什么字符相同時不需要操作因為word1[i-1] word2[j-1]這兩個字符已經(jīng)匹配只需要看前面的部分。3. 一維 DP 的prev變量prev保存的是dp[i-1][j-1]左上角的值因為dp[j-1]在當前行已經(jīng)被更新了不能直接用。總結(jié)要點說明核心思想dp[i][j]表示轉(zhuǎn)換的最少操作數(shù)狀態(tài)轉(zhuǎn)移相同dp[i-1][j-1]不同1 min(刪, 插, 換)初始化dp[i][0] idp[0][j] j時間復雜度O(m × n)空間復雜度O(n) 【動態(tài)規(guī)劃-5】72.編輯距離
題目描述給你兩個單詞word1和word2請返回將word1轉(zhuǎn)換成word2所使用的最少操作數(shù)。你可以對一個單詞進行如下三種操作插入一個字符刪除一個字符替換一個字符示例 1輸入word1 horse, word2 ros輸出3解釋horse - rorse (將 h 替換為 r) rorse - rose (刪除 r) rose - ros (刪除 e)示例 2輸入word1 intention, word2 execution輸出5解釋intention - inention (刪除 t) inention - enention (將 i 替換為 e) enention - exention (將 n 替換為 x) exention - exection (將 n 替換為 c) exection - execution (插入 u)解題思路方法一動態(tài)規(guī)劃核心思路狀態(tài)定義dp[i][j] 將word1的前i個字符轉(zhuǎn)換成word2的前j個字符所需的最少操作數(shù)。狀態(tài)轉(zhuǎn)移對于word1[i-1]和word2[j-1]情況1字符相同dp[i][j] dp[i-1][j-1] 不需要操作情況2字符不同dp[i][j] 1 min( dp[i-1][j], // 刪除 word1[i-1] dp[i][j-1], // 插入 word2[j-1] dp[i-1][j-1] // 替換 word1[i-1] 為 word2[j-1] )初始化dp[0][j] jword1 為空需要插入 j 個字符dp[i][0] iword2 為空需要刪除 i 個字符具體過程示例word1 horse, word2 rosdp: r o s 0 1 2 3 h 1 1 2 3 o 2 2 1 2 r 3 2 2 2 s 4 3 3 2 e 5 4 4 3 dp[5][3] 3 ?代碼實現(xiàn)寫法1二維 DPclass Solution { public: int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorvectorint dp(m 1, vectorint(n 1, 0)); // 初始化 for (int i 0; i m; i) dp[i][0] i; for (int j 0; j n; j) dp[0][j] j; // 狀態(tài)轉(zhuǎn)移 for (int i 1; i m; i) { for (int j 1; j n; j) { if (word1[i-1] word2[j-1]) { dp[i][j] dp[i-1][j-1]; } else { dp[i][j] 1 min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}); } } } return dp[m][n]; } };寫法2一維 DP空間優(yōu)化class Solution { public: int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorint dp(n 1, 0); // 初始化word1 為空 for (int j 0; j n; j) dp[j] j; for (int i 1; i m; i) { int prev dp[0]; // 保存 dp[i-1][j-1] dp[0] i; // dp[i][0] i for (int j 1; j n; j) { int temp dp[j]; // 保存 dp[i-1][j] if (word1[i-1] word2[j-1]) { dp[j] prev; } else { dp[j] 1 min({dp[j], dp[j-1], prev}); } prev temp; // 更新 prev } } return dp[n]; } };復雜度分析方法時間復雜度空間復雜度二維 DPO(m × n)O(m × n)一維 DPO(m × n)O(n)關鍵細節(jié)1. 三種操作對應哪些狀態(tài)操作狀態(tài)轉(zhuǎn)移含義刪除dp[i-1][j]刪除 word1[i-1] 后用前 i-1 個字符匹配 j 個插入dp[i][j-1]插入 word2[j-1] 后用 i 個字符匹配前 j-1 個替換dp[i-1][j-1]替換 word1[i-1] 為 word2[j-1] 后匹配前 i-1 和前 j-12. 為什么字符相同時不需要操作因為word1[i-1] word2[j-1]這兩個字符已經(jīng)匹配只需要看前面的部分。3. 一維 DP 的prev變量prev保存的是dp[i-1][j-1]左上角的值因為dp[j-1]在當前行已經(jīng)被更新了不能直接用。總結(jié)要點說明核心思想dp[i][j]表示轉(zhuǎn)換的最少操作數(shù)狀態(tài)轉(zhuǎn)移相同dp[i-1][j-1]不同1 min(刪, 插, 換)初始化dp[i][0] idp[0][j] j時間復雜度O(m × n)空間復雜度O(n)