动态规划之经典中的经典——公共最长子序列

╰+哭是因爲堅強的太久メ 2024-03-24 11:38 63阅读 0赞

##  ##

[点一点了解更多][Link 1]，动态规划，简单来说就是利用子结果来求下一次的结果，避免我们重复计算

--------------------

**目录**

一、动态规划

二、简单动态规划——青蛙跳台阶

三、经典动态规划——最长公共子序列问题

3.1最短公共超序列

--------------------

**一、动态规划**

> 动态规划，简单来说就是利用子结果来求下一次的结果，避免我们重复计算，子结果一般是用变量来保存，一般是用一维数组或者二维数组来保存。简单来说分三步：

> 1.  第一步：定义数组元素的含义，我们要学会怎么去定义数组dp\[\]，dp\[i\]代表什么意思？
> 2.  第二步：找出数组元素之间的关系式，当我们要计算dp\[n\]时，是可以利用dp\[n-1\],dp\[n-2\]....dp\[1\],来推出dp\[n\]，也就是可以利用子结果去推出新的元素值，重点就是找到数组元素之间的关系，例如dp\[n\] = dp\[n-1\]+dp\[n-2\]，这个就是他们的关系
> 3.  第三步：找出初始值，也就是最开始的值，例如dp\[1\],dp\[2\].....，有了初始值，根据关系式就可以推出dp\[n\]，而 dp\[n\] 的含义是由你来定义的。

## **二、简单动态规划——青蛙跳台阶** ##

> 问题：一只青蛙一次可以跳上一阶台阶，也可以跳上二阶。求该青蛙跳上一个n级的台阶总共有多少种跳法。

> 按照上面的三步，分别来求出dp数组的含义，初始值，dp\[n\]的关系式，dp\[n\] 一定会和 dp\[n-1\], dp\[n-2\]….存在某种关系的。
> 
> 因为跳台阶可以选择跳一级和跳俩级，那么青蛙到达第 n 级的台阶有两种方式，一种是从第 n-1 级跳上来，一种是从第 n-2 级跳上来。
> 
> 要求所有结果，所以**dp\[n\] = dp\[n-1\] + dp\[n-2\]**
> 
> 初始条件：dp\[1\] = 1,dp\[0\] = 0。因为0个台阶就有一种跳法，1个台阶也是一种跳法

int dpCount( int n ){
        if(n <= 1)
        return n;
        // 先创建一个数组来保存历史数据
        int[] dp = new int[n+1];
        // 给出初始值
        dp[0] = 0;
        dp[1] = 1;
        // 通过关系式来计算出 dp[n]
        for(int i = 2; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        // 把最终结果返回
        return dp[n];
    }

> 当 n = 2 时，dp\[2\] = dp\[1\] + dp\[0\] = 1。这显然是错误的，所以自己计算一下，计算量不大，所以dp\[2\] = 2,也就是说，在寻找初始值的时候，一定要注意不要找漏了，dp\[2\] 也算是一个初始值，不能通过公式计算得出。

## **三、经典动态规划——**最长公共子序列问题 ##

> 最长公共子序列问题是典型的二维动态规划问题。
> 
> 问题：
> 
> 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
> 
> 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
> 
> 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。  
> 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
> 
> [1143. 最长公共子序列 - 力扣（LeetCode）][1143. _ - _LeetCode]

> 首先考虑dp\[\]怎么定义，因为是俩个字符串，所以定义一个二维数组 dp 用来存储最长公共子序列的长度，其中 dp\[i\]\[j\] 表示字符串s1前i个字符和字符串s2前j个字符最长公共子序列的长度，考虑俩个下标，i与 j的值是否相等
> 
> 分俩种情况：
> 
> 1.  **`当s1[i] == s2[j]` ：f\[i\]\[j\] = f\[i−1\]\[j−1\]+1**
> 2.  **当`s1[i] != s2[j]`：f\[i\]\[j\] = max(f\[i−1\]\[j\],f\[i\]\[j−1\])**
> 
> ![e336e2d9d4fe41559822dc209e1f5f96.png][]

![70c2ada6d93c4f31a6f9ae8b5e53e2e5.png][]

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

![a5ecd1731133402fb5b8ff7859c7bbc4.png][]

#### 3.1最短公共超序列 ####

> 给出两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为子序列的最短字符串。如果答案不止一个，则可以返回满足条件的任意一个答案。
> 
> （如果从字符串 T 中删除一些字符（也可能不删除，并且选出的这些字符可以位于 T 中的 任意位置），可以得到字符串 S，那么 S 就是 T 的子序列）
> 
> [1092. 最短公共超序列 - 力扣（LeetCode）][1092. _ - _LeetCode]

![7723e4cb708c4d94afb5c78155d940ed.png][]

> ![041bcfc5b7f94d5b9bdd87abaaea7d73.png][]
> 
> 建立 DP 数组，dp\[i\]\[j\] 表示当字符串 str1 的位置 i 和字符串 str2 的位置 j 时的最长公共子序列。分为俩种情况：
> 
> 1.  当 str1\[i\] 和 str2\[j\] 字符相等时，我们只需要从上一个状态转移到当前状态即可，即计数加一：**f\[i\]\[j\] = f\[i−1\]\[j−1\]+1**
> 2.  当不相等时，**f\[i\]\[j\] = max(f\[i−1\]\[j\],f\[i\]\[j−1\])，如果 f\[i\]\[j\]=f\[i−1\]\[j\]，则将 str1\[i\] 加入到答案序列，然后i-1；如果 f\[i\]\[j\]=f\[i\]\[j-1\]，则将 str2\[j\] 加入到答案序列，然后j-1。**
> 3.  重复上述操作，直到 i=0 或j=0，然后将剩余的字符串加入到答案序列即可。

class Solution {
        public String shortestCommonSupersequence(String str1, String str2) {
            int m = str1.length(), n = str2.length();
            int[][] f = new int[m + 1][n + 1];
            for (int i = 1; i <= m; ++i) {
                for (int j = 1; j <= n; ++j) {
                    if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                        f[i][j] = f[i - 1][j - 1] + 1;
                    } else {
                        f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                    }
                }
            }
            int i = m, j = n;
            StringBuilder ans = new StringBuilder();
            while (i > 0 || j > 0) {
                if (i == 0) {
                    ans.append(str2.charAt(--j));
                } else if (j == 0) {
                    ans.append(str1.charAt(--i));
                } else {
                    if (f[i][j] == f[i - 1][j]) {
                        ans.append(str1.charAt(--i));
                    } else if (f[i][j] == f[i][j - 1]) {
                        ans.append(str2.charAt(--j));
                    } else {
                        ans.append(str1.charAt(--i));
                        --j;
                    }
                }
            }
            return ans.reverse().toString();
        }
    }

![7f45cb7f98164fde904dc15fd87a7c90.png][]

##  ##

[Link 1]: https://www.csdn.net/
[1143. _ - _LeetCode]: https://leetcode.cn/problems/longest-common-subsequence/
[e336e2d9d4fe41559822dc209e1f5f96.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/4a0fb644d80a42abb75b50e58876fc40.png
[70c2ada6d93c4f31a6f9ae8b5e53e2e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/ae83a88d9dcf4c41916bb23ae61a663f.png
[a5ecd1731133402fb5b8ff7859c7bbc4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/b3e8b2cdc3d34cbf880184d3cc4b188a.png
[1092. _ - _LeetCode]: https://leetcode.cn/problems/shortest-common-supersequence/
[7723e4cb708c4d94afb5c78155d940ed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/c62c4f7c7a2c4035a9c4d1e59828cc9e.png
[041bcfc5b7f94d5b9bdd87abaaea7d73.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/d8c7fd906ff44a579f17e79da5f21df6.png
[7f45cb7f98164fde904dc15fd87a7c90.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/047c7c408a6a40749ab0897eab8d6a6e.png