leetcode演算法之動態規劃（三）

今天來盤一盤 **動態規劃 ** 這類題目

這是最讓我頭疼的一類題目，一直不想做這類題目，這裡開始學習一下。

使用python刷題分類整理的筆記,請參考: //github.com/lxztju/leetcode-algorithm/tree/v1

動態規劃

動規就是以空間換取時間。

動態規劃常常適用於有重疊子問題和最優子結構性質的問題。

一些思考的套路： 遞歸 （自頂向下）——> 記憶化遞歸（自頂向下消除重複） ——> 動態規劃（自底而上）

  1. 最長遞增子序列
  • 300 最長上升子序列（medium）
  • 646 最長數對鏈（medium）
  • 376 擺動序列（medium）
  1. 最長公共子序列
  • 1143 最長公共子序列（medium）
  1. 字元串編輯
  • 583 兩個字元串的刪除操作（medium）
  • 72 編輯距離（hard）
  • 650 只有兩個鍵的鍵盤（medium）

5. 最長遞增子序列

300 最長上升子序列（medium）

  • dp[i]表示以第i元素為結尾的最長上升子列的長度
  • dp[i] = max(dp[j]) + 1 並且 nums[i] > nums[j],也就是針對所以小於i的dp子數組，如果nums[j] < nums[i] 那麼選擇其中最大的加一， 如果全部小於nums[i]，那麼dp[i] = 1
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 0);
        dp[0] = 1;
        for (int i = 1; i < n; i++){
            for (int j = 0; j < i; j++){
                if (nums[i] > nums[j]){
                    dp[i]  = max(dp[i], dp[j]);
                }
            }
            dp[i]++;
        }
    }
};

646 最長數對鏈（medium）

  • 與上一題類似
class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b){
        if (a[1] == b[1]) return a[0] < b[0];
        return a[1] < b[1];
    } 

    int findLongestChain(vector<vector<int>>& pairs) {
        int n = pairs.size();

        sort(pairs.begin(), pairs.end(), cmp);  

        vector<int> dp(n, 0);
        dp[0] = 1;
        for (int i = 1; i < n; i++){
            for (int j = 0; j < i; j++){
                if ( pairs[i][0] > pairs[j][1] )
                    dp[i] = max(dp[i], dp[j]);
            }
            dp[i]++;
        }

        return *max_element(dp.begin(), dp.end());
    }
};

376 擺動序列（medium）

  • 與前兩題一致， 這裡採用dp[i][0]表示以i為結尾的最長的序列最後一個差值為負數
  •   								dp[i][1]最後一個差值為正數

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

6. 最長公共子序列

1143 最長公共子序列（medium）

  • dp[i][j]表示text1的前i個字元， text2的前j個字元中二者的公共子序列的長度
  • 如果text[i] == text2[j] 那麼 dp[i][j] = dp[i-1][j-1]+1
  • 如果text1[i] != text2[j] 那麼： dp[i][j] = max(dp[i-1][j], dp[i][j-1])
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n=  text2.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 (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];
    }
};

7. 字元串編輯

583 兩個字元串的刪除操作（medium）

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

72 編輯距離（hard）

  • 設dp[i][j]為word1的前i個字元轉換為word2的前j個字元所需要的操作數。
  • 當word1[i] == word2[j]時候，dp[i][j] = dp[i-1][j-1]
  • 當word1[i] != word2[j]時候
    • 如果此時word1[i-1]與 word[j]已經轉換完成， 那麼此時刪除word1[i]即可 此時dp[i][j] = dp[i-1][j] + 1
    • 如果此時word1[i]與 word[j-1]已經轉換完成， 那麼此時插入word1[i]即可 此時dp[i][j] = dp[i][j-1] + 1
    • 如果此時word1[i-1]與 word[j-1]已經轉換完成， 那麼此時替換word1[i]即可 此時dp[i][j] = dp[i-1][j-1] + 1
    • 從這三種情況中取得最小值即可
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));

        // 空字元轉換為word2
        for (int j = 1; j <= n; j++)
            dp[0][j] = dp[0][j-1] + 1;
        // word1轉換為空字元
        for (int i = 1; i <= m; i++)
            dp[i][0] = dp[i-1][0] + 1;

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

650 只有兩個鍵的鍵盤（medium）

  • dp[i]表示列印i個A需要的最小的次數。
class Solution {
public:
    int minSteps(int n) {
        vector<int> dp(n+1, INT_MAX);
        dp[1] = 0;
        for (int i = 2; i <= n; i++){
            for (int j = 1; j < i; j++){
                if ( i % j == 0)
                    dp[i] = min(dp[i], dp[j] + i / j);
            }
        }
        return dp[n];
    }
};

更多分類刷題資料

Tags:

VirMach 便宜 VPS

QNews

QNews