一、最長(zhǎng)公共子序列

題目一：1143. 最長(zhǎng)公共子序列

1143. 最長(zhǎng)公共子序列

給定兩個(gè)字符串?text1?和?text2，返回這兩個(gè)字符串的最長(zhǎng)?公共子序列?的長(zhǎng)度。如果不存在?公共子序列?，返回?0?。

一個(gè)字符串的?子序列?是指這樣一個(gè)新的字符串：它是由原字符串在不改變字符的相對(duì)順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。

• 例如，"ace"?是?"abcde"?的子序列，但?"aec"?不是?"abcde"?的子序列。

兩個(gè)字符串的?公共子序列?是這兩個(gè)字符串所共同擁有的子序列。

定義一個(gè)二維數(shù)組dp，其中dp[i][j]代表text1中前i個(gè)字符與text2中前j個(gè)字符的最長(zhǎng)公共子序列的長(zhǎng)度。對(duì)于數(shù)組中的每個(gè)位置dp[i][j]，有兩種情況：

1. 如果text1[i-1] == text2[j-1]，則說(shuō)明這兩個(gè)字符匹配，可以在之前找到的最長(zhǎng)公共子序列的基礎(chǔ)上加1，即dp[i][j] = dp[i-1][j-1] + 1。
2. 如果text1[i-1] != text2[j-1]，則說(shuō)明這兩個(gè)字符不匹配，需要從兩個(gè)可能的最長(zhǎng)公共子序列中選擇較長(zhǎng)的一個(gè)，即dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

初始條件是dp[0][j] = 0和dp[i][0] = 0，因?yàn)槿绻渲幸粋€(gè)字符串為空，則最長(zhǎng)公共子序列的長(zhǎng)度為0。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length(), n = text2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }   
        }
    
        return dp[m][n];
    }
};

二、不相交的線

題目一：1035. 不相交的線

1035. 不相交的線

在兩條獨(dú)立的水平線上按給定的順序?qū)懴?nums1?和?nums2?中的整數(shù)。

現(xiàn)在，可以繪制一些連接兩個(gè)數(shù)字?nums1[i]?和?nums2[j]?的直線，這些直線需要同時(shí)滿足滿足：

• ?nums1[i] == nums2[j]
• 且繪制的直線不與任何其他連線（非水平線）相交。

請(qǐng)注意，連線即使在端點(diǎn)也不能相交：每個(gè)數(shù)字只能屬于一條連線。

以這種方法繪制線條，并返回可以繪制的最大連線數(shù)。

定義一個(gè)二維數(shù)組dp，其中dp[i][j]代表nums1中前i個(gè)元素和nums2中前j個(gè)元素可以形成的最大連線數(shù)。對(duì)于數(shù)組中的每個(gè)位置dp[i][j]，有兩種情況：

1. 如果nums1[i-1] == nums2[j-1]，說(shuō)明找到了一個(gè)匹配對(duì)，可以在之前找到的最大連線數(shù)的基礎(chǔ)上加1，即dp[i][j] = dp[i-1][j-1] + 1。
2. 如果nums1[i-1] != nums2[j-1]，說(shuō)明當(dāng)前的兩個(gè)元素不能形成連線，需要從之前的結(jié)果中選擇最大的那個(gè)，即dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

初始條件是dp[0][j] = 0和dp[i][0] = 0，因?yàn)槿绻渲幸粋€(gè)序列為空，則最大連線數(shù)為0。

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
    
        return dp[m][n];
    }
};

三、最大子數(shù)組和

題目一：53. 最大子數(shù)組和?

53. 最大子數(shù)組和

給你一個(gè)整數(shù)數(shù)組?nums?，請(qǐng)你找出一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。

子數(shù)組?是數(shù)組中的一個(gè)連續(xù)部分。

算法的核心思想是遍歷數(shù)組，同時(shí)維護(hù)兩個(gè)變量：currentSum表示到當(dāng)前元素為止的最大子數(shù)組和（包含當(dāng)前元素），maxSum表示遍歷到目前為止的最大子數(shù)組和。

對(duì)于數(shù)組中的每個(gè)元素，將其加到currentSum中，如果currentSum變成負(fù)數(shù)，就將currentSum重置為0，因?yàn)槿魏伟懊娌糠值淖訑?shù)組都不可能是最大子數(shù)組和。

同時(shí)，更新maxSum為currentSum和maxSum中的較大值。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-831896.html

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
    
        return dp[m][n];
    }
};

到了這里，關(guān)于Day46- 動(dòng)態(tài)規(guī)劃part14的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！