leetcode算法之动态规划（三）

• 2021 年 2 月 12 日
• AI
• C/C++/C#

今天来盘一盘 **动态规划 ** 这类题目

这是最让我头疼的一类题目，一直不想做这类题目，这里开始学习一下。

使用python刷题分类整理的笔记,请参考: //github.com/lxztju/leetcode-algorithm/tree/v1

动态规划

动规就是以空间换取时间。

动态规划常常适用于有重叠子问题和最优子结构性质的问题。

一些思考的套路： 递归 （自顶向下）——> 记忆化递归（自顶向下消除重复） ——> 动态规划（自底而上）

5. 最长递增子序列

• 300 最长上升子序列（medium）
• 646 最长数对链（medium）
• 376 摆动序列（medium）

6. 最长公共子序列

• 1143 最长公共子序列（medium）

7. 字符串编辑

• 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];
    }
};

更多分类刷题资料

• 微信公众号： 小哲AI

  

• GitHub地址： //github.com/lxztju/leetcode-algorithm

• csdn博客： //blog.csdn.net/lxztju

• 知乎专栏： //www.zhihu.com/column/c_1101089619118026752

• AI研习社专栏：//www.yanxishe.com/column/109