動態(tài)規(guī)劃

1.01背包

題目描述

有 n 個重量個價值分別為 w_i, v_i 的物品。
從這些物品中選出總重量不超過 W 的物品掷邦，使其總價值最大白胀。

輸入：
1 // 用例數(shù)
5 10 // 物品數(shù) 背包容量 N <= 1000 , V <= 1000
1 2 3 4 5 //價值
5 4 3 2 1 //重量

輸出：14

1.1 二維DP

  1. DP定義：dp[i][j] 從前 i 個物品中選取總重量不超過 j 的物品時總價值的最大值；
  2. DP初始：dp[0][j] = 0;
  3. DP轉(zhuǎn)移：
    • dp[i][j] = dp[i-1][j] if(j<w[i]), 當前剩余容量不夠放下第i個物品
    • dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
int max_value1(vector<int> v, vector<int> w, int V, int N){
    vector<vector<int>> dp(N+1, vector<int>(V+1, 0));
    for(int i=1;i<=N;i++){
        for(int j=0;j<=V;j++){
            if(w[i]>j) dp[i][j] = dp[i-1][j];
            else dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
        }
    }
    return dp[N][V];
}

int main(){
    int T;
    cin >> T;

    int N, V;
    cin >> N >> V;
    vector<int> v, w;
    v.push_back(0);
    w.push_back(0);
    int n;
    for(int i=0;i<N;i++){
        cin >> n;
        v.push_back(n);
    }

    for(int i=0;i<N;i++){
        cin >> n;
        w.push_back(n);
    }

    while(T){
        int res = max_value2(v, w, V, N);
        cout << res << endl;
        T--;
    }

    return 0;
}

1.2 一維DP

  1. DP定義：dp[j] 總重量不超過 j 的物品時總價值的最大值抚岗；
  2. DP初始：dp[j] = 0;
  3. DP轉(zhuǎn)移：dp[j] = max(dp[j], dp[j-w[i]] + v[i]) if(j>w[i])

int max_value2(vector<int> v, vector<int> w, int V, int N){
    vector<int> dp(V+1, 0);
    for(int i=1;i<=N;i++){
        for(int j=V;j>=w[i];j--){
            dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
        }
    }
    return dp[V];
}

2.完全背包

題目描述

01 背包中每個物品只有一個或杠，所以只存在選或不選；
完全背包中每個物品可以選取任意件宣蔚。

一維DP

  1. DP定義：dp[j] 總重量不超過 j 的物品時總價值的最大值向抢；
  2. DP初始：dp[j] = 0;
  3. DP轉(zhuǎn)移：dp[j] = max(dp[j], dp[j-w[i]] + v[i]) if(j>w[i])

int max_value(vector<int> v, vector<int> w, int V, int N){
    vector<int> dp(V+1, 0);
    for(int i=1;i<=N;i++){
        for(int j=w[i];j<=V;j++){
            dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
        }
    }
    return dp[V];
}

3. leetcode322-零錢兌換

題目描述

給定不同面額的硬幣 coins 和一個總金額 amount。編寫一個函數(shù)來計算可以湊成總金額所需的最少的硬幣個數(shù)胚委。如果沒有任何一種硬幣組合能組成總金額挟鸠，返回 -1。

輸入: coins = [1, 2, 5], amount = 11
輸出: 3
解釋: 11 = 5 + 5 + 1

DP求解

  1. DP定義：dp[i] : 組成總金額i時的最少硬幣數(shù)
  2. DP初始：
    • dp[0] = 0;
    • dp[i] = amount+1亩冬， i != 0
  3. DP轉(zhuǎn)移：dp[i] = min(dp[i-coins[j]]+1, dp[i]) ,if i>=coins[j];

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, amount+1);
        dp[0] = 0;
        sort(coins.begin(), coins.end());
        for(int i=0;i<=amount;i++){
            for(int j=0;j<coins.size();j++){
                if(i - coins[j]>=0) dp[i] = min(dp[i], 1 + dp[i - coins[j]]);
            }
        }
        return dp[amount]>amount ? -1 : dp[amount];
    }
};

4. leetcode518-零錢兌換II

題目描述

給定不同面額的硬幣和一個總金額艘希。寫出函數(shù)來計算可以湊成總金額的硬幣組合數(shù)。假設(shè)每一種面額的硬幣有無限個硅急。

輸入: amount = 5, coins = [1, 2, 5]
輸出: 4
解釋: 有四種方式可以湊成總金額:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

DP求解

  1. DP定義：dp[i] : 組成總金額 i 的方式
  2. DP初始：dp[0] = 1
  3. DP轉(zhuǎn)移：dp[i]=dp[i]+dp[i-coin];

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1, 0);
        dp[0] = 1;
        for(auto coin:coins ){
            for(int i=coin;i<=amount;i++){
                dp[i] += dp[i-coin];
            }
        }
        return dp[amount];
    }
};

5. 最長公共子序列

題目描述

對于兩個字符串覆享，請設(shè)計一個高效算法，求他們的最長公共子序列的長度营袜，這里的最長公共子序列定義為有兩個序列U1,U2,U3...Un和V1,V2,V3...Vn,其中Ui&ltUi+1撒顿，Vi&ltVi+1。且A[Ui] == B[Vi]荚板。
給定兩個字符串A和B凤壁，同時給定兩個串的長度n和m，請返回最長公共子序列的長度跪另。保證兩串長度均小于等于300拧抖。

輸入："1A2C3D4B56",10,"B1D23CA45B6A",12
輸出：6

DP求解

  1. DP定義：dp[i][j] : A[0:i]和B[0:j]的最長公共子序列的長度
  2. DP初始：dp[i][j] = 0 , i=0 or j=0
  3. DP轉(zhuǎn)移：
    • dp[i][j]=dp[i-1][j-1]+1 if A[i-1]==B[j-1];
    • dp[i][j]=dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

class LCS {
public:
    int findLCS(string A, int n, string B, int m) {
        vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(A[i-1]==B[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[n][m];
    }
};

6. 最長公共子串

題目描述

對于兩個字符串，請設(shè)計一個時間復(fù)雜度為O(m * n)的算法(這里的m和n為兩串的長度)免绿，求出兩串的最長公共子串的長度徙鱼。這里的最長公共子串的定義為兩個序列U1,U2,..Un和V1,V2,...Vn，其中Ui + 1 == Ui+1,Vi + 1 == Vi+1针姿，同時Ui == Vi。給定兩個字符串A和B厌衙，同時給定兩串的長度n和m距淫。

測試樣例：
輸入："1AB2345CD",9,"12345EF",7
輸出：返回：4

DP求解

  1. DP定義：dp[i][j] : A[0:i]和B[0:j]的最長公共子序列的長度
  2. DP初始：dp[i][j] = 0 , i=0||j=0
  3. DP轉(zhuǎn)移：dp[i][j]=dp[i-1][j-1]+1 if A[i-1]==B[j-1];

class LongestSubstring {
public:
    int findLongest(string A, int n, string B, int m) {
        vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
        int length = 0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(A[i-1]==B[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                length = max(length, dp[i][j]);
            }
        }
        return length;
    }
};

7. leetcode300-最長上升子序列

題目描述

給定一個無序的整數(shù)數(shù)組，找到其中最長上升子序列的長度婶希。

輸入: [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長的上升子序列是 [2,3,7,101]榕暇，它的長度是 4。

可能會有多種最長上升子序列的組合，你只需要輸出對應(yīng)的長度即可彤枢。

DP求解

  1. DP定義：dp[i] : 長度為 i 的 LIS 的最小尾元素
  2. DP初始：dp[i][j] = 0 , i=0||j=0
  3. DP轉(zhuǎn)移：
    • 二分查找 nums[j] 在 dp 中的lower_bound 位置
      • lower_bound 位置指的是序列中第一個大于等于 nums[j] 的元素所在的位置
    • 如果在末尾狰晚，則插入；反之則替換

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp;
        for(int i=0;i<nums.size();i++){
            int k = lower_bound(dp.begin(), dp.end(), nums[i]) - dp.begin();
            if(lower_bound(dp.begin(), dp.end(), nums[i]) != dp.end()) dp[k] = nums[i];
            else dp.push_back(nums[i]);
        }
        return dp.size();
    }
};

8. leetcode516-最長回文子序列

題目描述

給定一個字符串s缴啡，找到其中最長的回文子序列壁晒。可以假設(shè)s的最大長度為1000业栅。

輸入: "bbbab"
輸出: 4

DP求解

  1. DP定義：dp[i][j] : 字符串 s 在區(qū)間 [i:j] 上的子串的回文序列長度
  2. DP初始：dp[i][i] = 1
  3. DP轉(zhuǎn)移：
  • dp[i][j] = dp[i+1][j-1] + 2, if s[i] == s[j]
  • dp[i][j] = max(dp[i+1][j], dp[i][j-1]), else
    因為dp[i][j]=dp[i+1][j-1],所以 i 需要從字符串尾部開始遍歷秒咐，即逆序。

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));

        for(int i=0;i<n;i++) dp[i][i] = 1;

        for(int i=n-1;i>=0;i--){
            for(int j=i+1;j<n;j++){
                if(s[i]==s[j]) dp[i][j] = dp[i+1][j-1] + 2;
                else dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }

        return dp[0][n-1];
    }
};

9. leetcode5-最長回文子串序列

題目描述

給定一個字符串 s碘裕，找到 s 中最長的回文子串携取。你可以假設(shè) s 的最大長度為 1000。

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案帮孔。

DP求解

  1. DP定義：dp[i][j] : 字符串 s 在區(qū)間 [i:j] 上的子串是否是一個回文串
  2. DP初始：dp[i][i] = true
  3. DP轉(zhuǎn)移：
  • dp[i][j] = dp[i+1][j-1], if s[i] == s[j]
  • dp[i][j] = false, else
    用length記錄最長長度并用start_index記錄子串最長子串的開始位置雷滋。

class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for(int i=0;i<n;i++) dp[i][i] = true;

        int length=1;
        int start_index=0;

        for(int i=n-1;i>=0;i--){
            for(int j=i+1;j<n;j++){
                if(j-i<2) dp[i][j] = (s[i]==s[j]) ? true : false;
                else if(s[i]==s[j]) dp[i][j] = dp[i+1][j-1];
                if(dp[i][j]&&j-i+1>length){
                    start_index = i;
                    length = j - i + 1;
                }
            }
        }
        return s.substr(start_index, length);
    }
};

10. leetcode-53-最大連續(xù)子序列和

題目描述

給定一個整數(shù)數(shù)組 nums ，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素）文兢，返回其最大和晤斩。

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6禽作。

DP求解

  1. DP定義：dp[i]: 序列 nums 在區(qū)間 [:i] 上的最大子序列
  2. DP初始：dp[0] = nums[0]
  3. DP轉(zhuǎn)移:
  • dp[i] = dp[i-1] + nums[i], dp[i-1]>0
  • dp[i] = nums[i], else

res用以記錄最大值尸昧。注意到每次遞歸實際只用到了 dp[i-1]，因此實際只用一個變量即可旷偿。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max_num=INT_MIN;
        int temp=0;

        for(auto num:nums){
            if(temp>0) temp += num;
            else temp = num;

            max_num = max(max_num, temp);
        }
        return max_num;
    }
};

11. leetcode72-編輯距離

題目描述

給定兩個單詞 word1 和 word2烹俗，計算出將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 。你可以對一個單詞進行如下三種操作：插入一個字符萍程；刪除一個字符幢妄；替換一個字符

輸入: word1 = "horse", word2 = "ros"
輸出: 3
解釋:
horse -> rorse (將 'h' 替換為 'r')
rorse -> rose (刪除 'r')
rose -> ros (刪除 'e')

DP求解

  1. DP定義：dp[i][j]: 將 word1[0:i] 轉(zhuǎn)換為 word2[0:j] 的最少操作數(shù)
  2. DP初始：
  • dp[i][0] = i , 每次從 word1 刪除一個字符
  • dp[0][j] = j , 每次從 word2 刪除一個字符
  1. DP轉(zhuǎn)移:
  • dp[i][j] = dp[i-1][j-1] , if word1[i] = word2[j]
  • dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1, else

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(int i=0;i<=m;i++) dp[i][0] = i;
        for(int i=0;i<=n;i++) dp[0][i] = i;

        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] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
            }
        }
        return dp[m][n];
    }
};

12. 最大正方形

題目描述

在一個由 0 和 1 組成的二維矩陣內(nèi)，找到只包含 1 的最大正方形茫负，并返回其面積蕉鸳。

輸入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
輸出: 4

DP求解

  1. DP定義：dp[i][j]: 以 matrix[i][j] 為正方形右下角所能找到的最大正方形的邊長
  2. DP初始：
  • dp[i][0] = matrix[i][0] ,
  • dp[0][j] = matrix[0][j] ,
  1. DP轉(zhuǎn)移:
  • dp[i][j] = min({dp[i-1][j], dp[i-1][j], dp[i-1][j-1], }) +1, if matrix[i][j] == '1'
  • dp[i][j] = 0, else

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty())
            return 0;

        auto row = matrix.size();
        auto col = matrix[0].size();
        vector<vector<int> > dp(row, vector<int>(col, 0));

        int res = 0;
        for (int i = 0; i < row; i++) {
            dp[i][0] = matrix[i][0] - '0';
            res = max(res, dp[i][0]);
        }

        for (int j = 0; j < col; j++) {
            dp[0][j] = matrix[0][j] - '0';
            res = max(res, dp[0][j]);
        }

        for (int i=1; i<row; i++)
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == '0') dp[i][j] = 0;
                else {
                    dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
                    res = max(res, dp[i][j]);
                }
            }
        return res * res;
    }
};

13. leetcode10-正則表達式匹配

題目描述

給你一個字符串 s 和一個字符規(guī)律 p，請你來實現(xiàn)一個支持 '.' 和 '' 的正則表達式匹配忍法。'.' 匹配任意單個字符'' 匹配零個或多個前面的那一個元素所謂匹配潮尝，是要涵蓋 整個 字符串 s的，而不是部分字符串饿序。
說明:s 可能為空勉失，且只包含從 a-z 的小寫字母。p 可能為空原探，且只包含從 a-z 的小寫字母乱凿，以及字符 . 和 *顽素。

輸入: s = "aa" ， p = "a"
輸出: false
解釋: "a" 無法匹配 "aa" 整個字符串徒蟆。

DP求解

  1. DP定義：dp[i][j]: s[:i]和p[:j]是否匹配
  2. DP初始：dp[0][0] = 1
  3. DP轉(zhuǎn)移:
    寫起來麻煩胁出，看代碼把！
class Solution {
public:
    bool isMatch(string s, string p) {
        vector<vector<int>> dp(s.size()+1, vector<int>(p.size()+1, 0));
        dp[0][0]=1;
        for(int i=0;i<=s.size();i++){
            for(int j=1;j<=p.size();j++){
                if(i&&(s[i-1]==p[j-1]||p[j-1]=='.')) dp[i][j] = dp[i-1][j-1];
                else if(p[j-1]=='*'&&j!=1){
                    if(i==0) dp[i][j] = dp[i][j-2];
                    else if(s[i-1]==p[j-2]||p[j-2]=='.') dp[i][j] = max(dp[i][j-2], dp[i-1][j]);
                    else dp[i][j] = dp[i][j-2];
                }
            }
        }
        return dp[s.size()][p.size()];
    }
};
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末段审，一起剝皮案震驚了整個濱河市全蝶，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌戚哎，老刑警劉巖裸诽，帶你破解...
    沈念sama閱讀 221,576評論 6贊 515
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異型凳，居然都是意外死亡丈冬，警方通過查閱死者的電腦和手機，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,515評論 3贊 399
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進店門甘畅，熙熙樓的掌柜王于貴愁眉苦臉地迎上來埂蕊，“玉大人，你說我怎么就攤上這事疏唾⌒钛酰” “怎么了？”我有些...
    開封第一講書人閱讀 168,017評論 0贊 360
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵槐脏，是天一觀的道長喉童。 經(jīng)常有香客問我，道長顿天，這世上最難降的妖魔是什么堂氯？ 我笑而不...
    開封第一講書人閱讀 59,626評論 1贊 296
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任，我火速辦了婚禮牌废，結(jié)果婚禮上咽白，老公的妹妹穿的比我還像新娘。我一直安慰自己鸟缕，他們只是感情好晶框，可當我...
    茶點故事閱讀 68,625評論 6贊 397
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布。 她就那樣靜靜地躺著懂从，像睡著了一般授段。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上番甩，一...
    開封第一講書人閱讀 52,255評論 1贊 308
  • 城市分裂傳說
    那天畴蒲，我揣著相機與錄音，去河邊找鬼对室。 笑死模燥，一個胖子當著我的面吹牛，可吹牛的內(nèi)容都是我干的掩宜。 我是一名探鬼主播蔫骂，決...
    沈念sama閱讀 40,825評論 3贊 421
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼牺汤！你這毒婦竟也來了辽旋？” 一聲冷哼從身側(cè)響起，我...
    開封第一講書人閱讀 39,729評論 0贊 276
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤檐迟，失蹤者是張志新（化名）和其女友劉穎补胚，沒想到半個月后，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體追迟，經(jīng)...
    沈念sama閱讀 46,271評論 1贊 320
  • ?護林員之死
    正文 獨居荒郊野嶺守林人離奇死亡溶其，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,363評論 3贊 340
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了敦间。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片瓶逃。...
    茶點故事閱讀 40,498評論 1贊 352
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖廓块，靈堂內(nèi)的尸體忽然破棺而出厢绝，到底是詐尸還是另有隱情，我是刑警寧澤带猴，帶...
    沈念sama閱讀 36,183評論 5贊 350
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布胸嘁，位于F島的核電站，受9級特大地震影響辞友，放射性物質(zhì)發(fā)生泄漏躲舌。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點故事閱讀 41,867評論 3贊 333
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一贷掖、第九天 我趴在偏房一處隱蔽的房頂上張望嫡秕。 院中可真熱鬧，春花似錦苹威、人聲如沸昆咽。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,338評論 0贊 24
  • 一樁弒父案牙甫，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽掷酗。三九已至，卻和暖如春窟哺，著一層夾襖步出監(jiān)牢的瞬間泻轰，已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,458評論 1贊 272
  • 情欲美人皮
    我被黑心中介騙來泰國打工且轨， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留浮声，地道東北人虚婿。 一個月前我還...
    沈念sama閱讀 48,906評論 3贊 376
  • 代替公主和親
    正文 我出身青樓，卻偏偏與公主長得像泳挥，于是被迫代替她去往敵國和親然痊。 傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當晚...
    茶點故事閱讀 45,507評論 2贊 359