【算法篇】逐步理解動態規劃模型7（兩個數組dp問題）

目錄

兩個數組dp問題

1.最長公共子序列

2.不同的子序列

3.通配符匹配

????????本文旨在通過對力扣上三道題進行講解來讓大家對使用動態規劃解決兩個數組的dp問題有一定思路，培養大家對狀態定義，以及狀態方程書寫的思維。

順序：

題目鏈接-》算法思路-》代碼呈現

兩個數組dp問題

動態規劃類題目解題步驟：

  1. 依據題目進行狀態表示(dp[i]的含義)
  2. 寫出狀態轉移方程(類似于dp[i]=dp[i-1]+dp[i-2])
  3. 為防止填表時數組越界，對dp表進行初始化（dp[0]=dp[1]=1）
  4. 搞清楚填表順序（從前往后或者從后往前）
  5. 利用dp表返回問題答案

1.最長公共子序列

題目鏈接：

https://leetcode.cn/problems/longest-common-subsequence/

算法思路：

1. 狀態表?：
????????對于兩個數組的動態規劃，我們的定義狀態表?的經驗就是：
  1. 選取第?個數組 [0, i] 區間以及第?個數組 [0, j] 區間作為研究對象；
  2. 結合題?要求，定義狀態表?。
在這道題中，我們根據定義狀態表?為：
dp[i][j] 表?： s1 的 [0, i] 區間以及 s2 的 [0, j] 區間內的所有的?序列中，最?公共?序列的?度。
2. 狀態轉移?程：
????????分析狀態轉移?程的經驗就是根據「最后?個位置」的狀況，分情況討論。
對于 dp[i][j] ，我們可以根據 s1[i] 與 s2[j] 的字符分情況討論：
1.? 兩個字符相同， s1[i] = s2[j] ：那么最?公共?序列就在 s1 的 [0, i - 1] 及 s2 的 [0, j - 1] 區間上找到?個最?的，然后再加上 s1[i] 即可。因此dp[i][j] = dp[i - 1][j - 1] + 1 ；
2. 兩個字符不相同， s1[i] != s2[j] ：那么最?公共?序列?定不會同時以 s1[i]和 s2[j] 結尾。那么我們找最?公共?序列時，有下?三種策略：
  • 去 s1 的 [0, i - 1] 以及 s2 的 [0, j] 區間內找：此時最??度為 dp[i - 1][j] ；
  • 去 s1 的 [0, i] 以及 s2 的 [0, j - 1] 區間內找：此時最??度為 dp[i ] [j - 1] ；
  • 去 s1 的 [0, i - 1] 以及 s2 的 [0, j - 1] 區間內找：此時最??度為dp[i - 1][j - 1] 。
我們要三者的最?值即可。但是我們細細觀察會發現，第三種包含在第?種和第?種情況??，但是我們求的是最?值，并不影響最終結果。因此只需求前兩種情況下的最?值即可。
綜上，狀態轉移?程為：
if(s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1 ;
if(s1[i] != s2[j]) dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) 。
3. 初始化：
  1. 「空串」是有研究意義的，因此我們將原始 dp 表的規模多加上??和?列，表?空串。
  2. 引?空串后，??的?便我們的初始化。
  3. 但也要注意「下標的映射關系」，以及??的值要「保證后續填表是正確的」。
當 s1 為空時，沒有?度，同理 s2 也是。因此第??和第?列??的值初始化為 0 即可保證后續填表是正確的。
4. 填表順序：
????????根據「狀態轉移?程」得：從上往下填寫每??，每??從左往右。
5. 返回值：
????????根據「狀態表?」得：返回 dp[m][n] 。

代碼呈現：

class Solution {public int longestCommonSubsequence(String text1, String text2) {int re=0;char[] s=text1.toCharArray();char[] s1=text2.toCharArray();int m=s.length,n=s1.length;int[][] dp=new int[m+1][n+1];for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(s[i-1]==s1[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 dp[m][n];}
}

2.不同的子序列

題目鏈接：

https://leetcode.cn/problems/distinct-subsequences/

算法思路：

1. 狀態表?：
????????對于兩個字符串之間的 dp 問題，我們?般的思考?式如下：
  1. 選取第?個字符串的 [0, i] 區間以及第?個字符串的 [0, j] 區間當成研究對象，結合題?的要求來定義「狀態表?」；
  2. 然后根據兩個區間上「最后?個位置的字符」，來進?「分類討論」，從?確定「狀態轉移?程」。
我們可以根據上?的策略，解決?部分關于兩個字符串之間的 dp 問題。
dp[i][j] 表?：在字符串 s 的 [0, j] 區間內的所有?序列中，有多少個 t 字符串 [0,i] 區間內的?串。
2. 狀態轉移?程：
?????????規矩，根據「最后?個位置」的元素，結合題?要求，分情況討論：
1. 當 t[i] == s[j] 的時候，此時的?序列有兩種選擇：
  • ?種選擇是：?序列選擇 s[j] 作為結尾，此時相當于在狀態 dp[i - 1][j - 1]中的所有符合要求的?序列的后?，再加上?個字符 s[j] （請?家結合狀態表?，好好理解這句話），此時 dp[i][j] = dp[i - 1][j - 1] ；
  • 另?種選擇是：我就是任性，我就不選擇 s[j] 作為結尾。此時相當于選擇了狀態dp[i][j - 1] 中所有符合要求的?序列。我們也可以理解為繼承了上個狀態??的求得的?序列。此時 dp[i][j] = dp[i][j - 1] ；
兩種情況加起來，就是 t[i] == s[j] 時的結果。
2. 當 t[i] != s[j] 的時候，此時的?序列只能從 dp[i][j - 1] 中選擇所有符合要求的?序列。只能繼承上個狀態??求得的?序列， dp[i][j] = dp[i][j - 1] ；
綜上所述，狀態轉移?程為：
  • 所有情況下都可以繼承上?次的結果： dp[i][j] = dp[i][j - 1] ；
  • 當 t[i] == s[j] 時，可以多選擇?種情況： dp[i][j] += dp[i - 1][j - 1]
3. 初始化：
  1. 「空串」是有研究意義的，因此我們將原始 dp 表的規模多加上??和?列，表?空串。
  2. 引?空串后，??的?便我們的初始化。
  3. 但也要注意「下標的映射關系」，以及??的值要「保證后續填表是正確的」。
當 s 為空時， t 的?串中有?個空串和它?樣，因此初始化第??全部為 1 。
4. 填表順序：
????????「從上往下」填每??，每??「從左往右」。
5. 返回值：
????????根據「狀態表?」，返回 dp[m][n] 的值。
本題有?個巨惡?的地?，題?上說結果不會超過 int 的最?值，但是實際在計算過程會會超。為
了避免報錯，我們選擇 double 存儲結果。

代碼呈現：

class Solution {public int numDistinct(String s, String t) {int MOD=1000000007;s=" "+s;t=" "+t;char[] s1=s.toCharArray();char[] s2=t.toCharArray();int n=s1.length;int m=s2.length;int[][] dp=new int[n][m];for(int i=0;i<n;i++){dp[i][0]=1;}for(int i=1;i<n;i++){for(int j=1;j<m;j++){dp[i][j]=dp[i-1][j];if(s1[i]==s2[j]){dp[i][j]+=dp[i-1][j-1];}}}return dp[n-1][m-1];}
}

3.通配符匹配

題目鏈接：

https://leetcode.cn/problems/wildcard-matching/

算法思路：

1. 狀態表?：
????????對于兩個字符串之間的 dp 問題，我們?般的思考?式如下：
  1. 選取第?個字符串的 [0, i] 區間以及第?個字符串的 [0, j] 區間當成研究對象，結合題?的要求來定義「狀態表?」；
  2. 然后根據兩個區間上「最后?個位置的字符」，來進?「分類討論」，從?確定「狀態轉移?程」。
我們可以根據上?的策略，解決?部分關于兩個字符串之間的 dp 問題。
因此，我們定義狀態表?為：dp[i][j] 表?： p 字符串 [0, j] 區間內的?串能否匹配字符串 s 的 [0, i] 區間內的?串。
2. 狀態轉移?程：
?????????規矩，根據最后?個位置的元素，結合題?要求，分情況討論：
1. 當 s[i] == p[j] 或 p[j] == '?' 的時候，此時兩個字符串匹配上了當前的?個字符，只能從 dp[i - 1][j - 1] 中看當前字符前?的兩個?串是否匹配。只能繼承上個狀態中的匹配結果， dp[i][j] = dp[i][j - 1] ；
2. 當 p[j] == '*' 的時候，此時匹配策略有兩種選擇：
  • ?種選擇是： * 匹配空字符串，此時相當于它匹配了?個寂寞，直接繼承狀態 dp[i][j - 1] ，此時 dp[i][j] = dp[i][j - 1] ；
  • 另?種選擇是： * 向前匹配 1 ~ n 個字符，直?匹配上整個 s1 串。此時相當于從 dp[k][j - 1] (0 <= k <= i) 中所有匹配情況中，選擇性繼承可以成功的情況。此時 dp[i][j] = dp[k][j - 1] (0 <= k <= i) ；
3. 當? p[j] 不是特殊字符，且不與 s[i] 相等時，?法匹配。三種情況加起來，就是所有可能的匹配結果。
綜上所述，狀態轉移?程為：
  • 當 s[i] == p[j] 或 p[j] == '?' 時： dp[i][j] = dp[i][j - 1] ；
  • 當 p[j] == '*' 時，有多種情況需要討論： dp[i][j] = dp[k][j - 1] (0 <=k <= i) ；
優化：當我們發現，計算?個狀態的時候，需要?個循環才能搞定的時候，我們要想到去優化。優
化的?向就是??個或者兩個狀態來表?這?堆的狀態。通常就是把它寫下來，然后?數學的?式
做?下等價替換：
當 p[j] == '*' 時，狀態轉移?程為：
dp[i][j] = dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 2][j - 1]
......
我們發現 i 是有規律的減?的，因此我們去看看 dp[i - 1][j] ：
dp[i - 1][j] = dp[i - 1][j - 1] || dp[i - 2][j - 1] || dp[i - 3][j - 1] ...... 我們驚奇的發現， dp[i][j] 的狀態轉移?程??除了第?項以外，其余的都可以? dp[i - 1][j] 替代。因此，我們優化我們的狀態轉移?程為： dp[i][j] = dp[i - 1][j] || dp[i][j - 1] 。
3. 初始化：
????????由于 dp 數組的值設置為是否匹配，為了不與答案值混淆，我們需要將整個數組初始化為false 。
由于需要?到前??和前?列的狀態，我們初始化第??、第?列即可。
  • dp[0][0] 表?兩個空串能否匹配，答案是顯然的， 初始化為 true 。
  • 第??表? s 是?個空串， p 串和空串只有?種匹配可能，即 p 串表?為 "***" ，此時 也相當于空串匹配上空串。所以，我們可以遍歷 p 串，把所有前導為 "*" 的 p ?串和空串 的 dp 值設為 true 。
  • 第?列表? p 是?個空串，不可能匹配上 s 串，跟隨數組初始化即可。
4. 填表順序：
????????從上往下填每??，每??從左往右。
5. 返回值：
????????根據狀態表?，返回 dp[m][n] 的值。

代碼呈現：

class Solution {public boolean isMatch(String s, String p) {s=" "+s;p=" "+p; char[] s1=s.toCharArray();char[] s2=p.toCharArray();int n=s1.length;int m=s2.length;boolean[][] dp=new boolean[n][m];dp[0][0]=true;for(int i=1;i<m;i++){if(s2[i]=='*'){dp[0][i]=dp[0][i-1];}}for(int i=1;i<n;i++){for(int j=1;j<m;j++){if(s2[j]=='?'||s1[i]==s2[j]){dp[i][j]=dp[i-1][j-1];}if(s2[j]=='*'){dp[i][j]=dp[i][j-1]||dp[i-1][j];}}}return dp[n-1][m-1];}
}

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

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

相關文章

什么是 HTTP Range 請求（范圍請求）

什么是 HTTP Range 請求（范圍請求）

HTTP Range 請求&#xff0c;即范圍請求&#xff0c;是一種 HTTP 請求方法&#xff0c;允許客戶端請求資源的部分數據。這種請求在處理大型文件&#xff08;如視頻、音頻、或大文件下載&#xff09;時特別有用&#xff0c;因為它可以有效地進行斷點續傳和按需加載數據&#xff…
閱讀更多...
java集合（十） ---- LinkedList 類

java集合（十） ---- LinkedList 類

目錄 十、LinkedList 類 10.1 位置 10.2 特點 10.3 與 ArrayList 的區別 10.4 構造方法 10.5 常用方法 十、LinkedList 類 10.1 位置 LinkedList 類位于 java.util 包下 10.2 特點 是 List 接口的實現類是 Deque 接口的實現類底層使用雙向循環鏈表結構 10.3 與 Arra…
閱讀更多...
kafka消費的模式及消息積壓處理方案

kafka消費的模式及消息積壓處理方案

目錄 1、kafka消費的流程 2、kafka的消費模式 2.1、點對點模式 2.2、發布-訂閱模式 3、consumer消息積壓 3.1、處理方案 3.2、積壓量 4、消息過期失效 5、kafka注意事項 Kafka消費積壓(Consumer Lag)是指消費者處理消息的速度跟不上生產者發送消息的速度&#xff0c;導致消息在…
閱讀更多...
RAG實踐：Routing機制與Query Construction策略

RAG實踐：Routing機制與Query Construction策略

Routing機制與Query Construction策略 前言RoutingLogical RoutingChatOpenAIStructuredRouting DatasourceConclusion Semantic RoutingEmbedding & LLMPromptRounting PromptConclusion Query ConstructionGrab Youtube video informationStructuredPrompt GithubReferen…
閱讀更多...
基于python的web系統界面登錄

基于python的web系統界面登錄

#讓我們的電腦可以支持服務訪問 #需要一個web框架 #pip install Flask from flask import Flask, render_template,request from random import randint app Flask(__name__) app.route(/index) def index():uname request.args.get("uname")return f"主頁&am…
閱讀更多...
MATLAB Simulink 終極入門指南：從零設計智能控制系統

MATLAB Simulink 終極入門指南：從零設計智能控制系統

為什么工程師都愛Simulink？ 想象一下：不寫一行代碼就能設計機器人控制器、飛行算法甚至核反應堆！ MATLAB Simulink正是這樣的可視化神器。全球70%的汽車ECU、航天器控制系統用它開發。本文將帶你從零設計一個智能溫控系統，融入創新性的模糊PID控制，并生成可部署的C代碼！…
閱讀更多...
vue3 javascript 復雜數值計算操作技巧

vue3 javascript 復雜數值計算操作技巧

在Vue 3中處理復雜數值計算&#xff0c;你可以采用多種策略來確保代碼的可讀性、可維護性和性能。以下是一些實用的技巧和最佳實踐&#xff1a; 1. 使用計算屬性&#xff08;Computed Properties&#xff09; Vue 3的computed屬性非常適合處理復雜的數值計算。它們是基于響應…
閱讀更多...
26.【.NET8 實戰--孢子記賬--從單體到微服務--轉向微服務】--單體轉微服務--角色權限管理

26.【.NET8 實戰--孢子記賬--從單體到微服務--轉向微服務】--單體轉微服務--角色權限管理

在現代企業級應用中&#xff0c;角色權限管理是保障系統安全和提升用戶體驗的核心基礎功能。一個高效的角色權限系統不僅能夠有效防止越權訪問&#xff0c;還能簡化系統的維護和擴展。本文將系統性介紹角色權限管理的核心實現思路&#xff0c;包括架構設計、性能優化、安全機制…
閱讀更多...
[VSCode] VSCode 設置 python 的編譯器

[VSCode] VSCode 設置 python 的編譯器

VSCode 設置 python 的編譯器 快捷鍵&#xff1a;CTRL SHIFT P 彈出 VSCode 的命令框輸入 Python : select Interpretor選擇自己需要的 python 環境&#xff1b;如 python 3.8 或者 python 3.10 版本
閱讀更多...
基于PEMFC質子交換膜燃料電池系統的simulink建模與仿真

基于PEMFC質子交換膜燃料電池系統的simulink建模與仿真

目錄 1.課題概述 2.系統仿真結果 3.核心程序 4.系統仿真參數 5.系統原理簡介 6.參考文獻 7.完整工程文件 1.課題概述 本課題是一個燃料電池&#xff08;大概率是質子交換膜燃料電池&#xff0c;PEMFC &#xff09;的數學模型仿真框圖&#xff0c;用于模擬燃料電池的電特…
閱讀更多...
git-build-package 工具代碼詳細解讀

git-build-package 工具代碼詳細解讀

git-build-package&#xff08;gbp&#xff09;是一個用于從 Git 倉庫管理 Debian 軟件包的工具&#xff0c;其代碼架構和實現原理體現了對 Git 版本控制系統和 Debian 打包流程的深度整合。以下是對其代碼的詳細解讀&#xff1a; 代碼架構設計 gbp 的代碼架構設計圍繞其核心…
閱讀更多...
如何使用ChatGPT快速完成一篇論文初稿？

如何使用ChatGPT快速完成一篇論文初稿？

2小時寫完論文初稿&#xff0c;學境思源&#xff0c;聽起來是不是有點不真實&#xff1f;一鍵生成論文初稿&#xff01;但如果你有一個清晰的框架、良好的寫作節奏&#xff0c;acaids.com。再配合像ChatGPT這樣的寫作助手——真的可以做到。 這篇文章就是手把手告訴你&#xf…
閱讀更多...
Docker PowerJob

Docker PowerJob

1. Docker PowerJob 1. 拉取PowerJob服務端鏡像 docker pull tjqq/powerjob-server:4.3.92. 創建數據卷目錄用于持久化數據 mkdir -p /home/docker/powerjob/logs mkdir -p /home/docker/powerjob/data mkdir -p /home/docker/powerjob/server mkdir -p /home/docker/powerjob…
閱讀更多...
Python數據可視化：NumPy生成與Matplotlib折線圖繪制

Python數據可視化：NumPy生成與Matplotlib折線圖繪制

一、數據生成與可視化概述 在數據分析和科學計算領域，Python已成為最受歡迎的編程語言之一。這主要得益于其豐富的數據處理庫和強大的可視化工具。數據可視化是將抽象數據轉化為直觀圖形表示的過程，它能夠幫助我們發現數據中的模式、趨勢和異常值，從而做出更明智的決策。 …
閱讀更多...
26.多表查詢

26.多表查詢

1.笛卡爾集 創建倆表&#xff1a; -- 創建部門表&#xff08;dept&#xff09; use mysql_learn CREATE TABLE dept (deptno INT PRIMARY KEY, dname VARCHAR(50) NOT NULL, loc VARCHAR(50) );-- 創建員工表&#xff08;emp&#xff09; CREATE TABLE emp (em…
閱讀更多...
深度學習題目（僅供參考）

深度學習題目（僅供參考）

一、注意力和transformer 一、選擇題 注意力機制的核心步驟不包括&#xff1f; A. 計算注意力分布 B. 加權平均輸入信息 C. 隨機丟棄部分輸入 D. 打分函數計算相關性 答案&#xff1a;C&#xff08;硬性注意力雖隨機選擇輸入&#xff0c;但核心步驟仍為分布計算與加權&#xf…
閱讀更多...
WebWorker：提升前端性能的多線程利器

WebWorker：提升前端性能的多線程利器

簡介 在現代Web開發中&#xff0c;隨著應用越來越復雜&#xff0c;JavaScript的單線程模型開始顯現其局限性。Web Workers的出現為解決這一問題提供了優雅的方案&#xff0c;它允許開發者在后臺線程中運行腳本&#xff0c;而不會影響主線程的性能。 Web Workers是HTML5標準的…
閱讀更多...
milvus教程：collection和scheme

milvus教程：collection和scheme

環境配置&#xff1a;可以看上一節 一.數據庫使用 連接 Milvus Standalone創建數據庫 my_database_1&#xff08;無額外屬性&#xff09;創建數據庫 my_database_2&#xff08;設置副本數為 3&#xff09;列出所有數據庫查看默認數據庫&#xff08;default&#xff09;詳情修…
閱讀更多...
14：00開始面試，14：06就出來了，問的問題有點變態。。。

14：00開始面試，14：06就出來了，問的問題有點變態。。。

從小廠出來&#xff0c;沒想到在另一家公司又寄了。 到這家公司開始上班&#xff0c;加班是每天必不可少的&#xff0c;看在錢給的比較多的份上&#xff0c;就不太計較了。沒想到6月一紙通知&#xff0c;所有人不準加班&#xff0c;加班費不僅沒有了&#xff0c;薪資還要降40%…
閱讀更多...
Electron（01）

Electron（01）

Electron Electron是什么 electron可以使用前端技術開發桌面應用&#xff0c;跨平臺性&#xff0c;開發一套應用&#xff0c;可以打包到三個平臺。 electron結合Chromium&#xff08;谷歌內核&#xff09;和 Node.js 和Native Api 當使用 Electron 時&#xff0c;很重要的一…
閱讀更多...
最新文章

Copyright @ 2022~2023