动态规划

ryluo 2020-08-22 10:37:10

最长连续递增序列(674)

image-20200821140540872


题目分析:

需要注意的是连续,相当于是子串或者子数组。

动态规划:

  1. 状态定义:$f[i]$表示数组$[0, i]$的连续递增序列的最大长度
  2. 状态计算:
    1. 子集划分:在进行转台计算之前需要思考,在当前定义的状态下,如何将问题划分成几个子集,最终的结果是这些子集的哪些属性。在考虑将问题划分成子集的时候,一般从当前状态或者当前状态的前一个,或前多个状态考虑划分。例如本题中,可以从$nums[i]$是否包含这个角度进行子集的划分:
    2. 状态计算:包含$nums[i]$,此时的状态方程可以表示为:$f[i] = f[i - 1] + 1$; 当不包含$nums[i]$,那么由于连续性,此时的$f[i]=1$(相当于是从本身重新开始计算),最后对这两个子集中的所有取值取$max$就是最终需要返回的结果
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        if (!n) return 0;
        int f[n];
        for(int i = 0; i < n; i++){
            if(i > 0 && nums[i - 1] < nums[i]) f[i] = f[i - 1] + 1;
            else f[i] = 1;
            ans = max(ans, f[i]);
        }
        return ans;
    }
};


最长回文子串(5)

image-20200821142856251


题目分析:

首先需要知道回文子串的定义,就是子串沿着中间某个字符或者两个字符中间是轴对称的。

动态规划:

  1. 状态定义:$f[i][j]$ ,表示字符串$s[i, … j]$是否是回文,其中的值是一个bool值。
  2. 状态计算:
    1. 子集的划分:可以通过$[i, j]$中字符串的数量来进行子集的划分,只有一个字符,只有两个字符,大于两个字符这三种情况
    2. 状态计算:只有一个字符$f[i][j]$是回文,只有两个字符,判断这两个字符是否相等,如果相等的话就是回文,大于两个字符,判断该字符去掉首尾之后是否是回文,如果是回文,在此基础上再判断首尾字符是否相等,如果相等则是回文,否则不是回文

为了少处理边界问题,这里通过遍历子串的长度和起始位置得到$i,j$的值

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> f(n, vector<bool>(n));
        int start = 0, len = 0;

        for(int i = 1; i <= n; i ++){ // 枚举字符串的长度
            for(int l = 0; l + i - 1 < n; l ++){ // 枚举起点
                int r = l + i - 1;
                if(i == 1) f[l][r] = true;
                else if(i == 2) f[l][r] = (s[l] == s[r]); 
                else f[l][r] = f[l + 1][r - 1] && s[l] == s[r];

                if(f[l][r] && len <= r - l + 1)
                    len = r - l + 1, start = l;
            }
        }

        return s.substr(start, len); 
    }
};


最长回文子序列(516)

image-20200821151538116


题目分析:

子序列与子串的区别,前者可以不连续,这种情况下划分子集的时候需要考虑当前状态之前的所有状态。

动态规划:

  1. 状态定义:$f[i][j]$, 表示$[i, j]$字符串中的最长回文子序列的长度
  2. 状态计算:
    1. 集合划分:从$s[i]$和$s[j]$的关系进行集合划分,如果$s[i] == s[j]$即不等的情况
    2. 状态计算:若$s[i] == s[j]$,$f[i][j] = f[i+1][j-1] + 2$,如果不等只取头尾中的一个,分别是$f[i+1][j]$或$f[i][j-1]$,这三者中的最大值。
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>> f(n, vector<int>(n));

        for(int i = n - 1; i >= 0; i --){
            f[i][i] = 1; // 当i=n-1时,j=n越界了不会进行计算,此时初始化的f[i][i]=0,实际是1
            for(int j = i + 1; j < n; j++){
                if(s[i] == s[j]) f[i][j] = f[i + 1][j - 1] + 2;
                else f[i][j] = max(f[i + 1][j], f[i][j - 1]); 
            }
        }
        return f[0][n - 1];
    }
};


编辑距离(72)

image-20200821153510737


题目分析:

要将一个字符串通过三种编辑方式(插入,删除,替换)变成另一个字符串,说明其中一个字符是不需要变动的,只需要操作一个字符即可。

动态规划:

  1. 状态定义:$f[i][j]$表示将s1的$[1,… i]$个字符变成s2的第$[1,… j]$字符所需要的最少操作数
  2. 状态计算:
    1. 集合划分,由于这里对与s1中第i个字符的操作总共有三种不同的方式,所以可以根据这三种不同的操作方式划分子集
    2. 状态计算:
      • 删除:说明此时的$s1[1,…i]$与$s2[1,…j]$已经是匹配好的,此时的$f[i][j]=f[i-1][j]+1$
      • 插入:说明此时的$s1[1,i]$与$s2[1,…j -1]$ 是匹配的,此时的$f[i][j]=f[i][j-1]+1$
      • 替换:说明此时的$s1[1,i-1]$与$s2[1,…j-1]$ 是匹配的,但是在这种情况下需要判断$s[i]$是否等于$s[j]$,如果相等的话$f[i][j]=f[i-1][j-1]$(也就是不需要任何操作),否则,$f[i][j]=f[i-1][j-1] + 1$,以上三种情况的编辑取次数最少的一个
class Solution {
public:
    int minDistance(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        vector<vector<int>> f(m + 1, vector<int>(n + 1));

        for(int i = 0; i <= m; i++) f[i][0] = i; // 插入操作
        for(int i = 0; i <= n; i++) f[0][i] = i; // 删除操作

        for(int i = 1; i <= m; i ++){
            for(int j = 1; j <= n; j++){
                f[i][j] = min(f[i][j - 1] + 1, f[i - 1][j] + 1);
                if(s1[i - 1] == s2[j - 1]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
                else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
            }   
        }

        return f[m][n];
    }
};


打家劫舍(198)



题目分析:

本质上是一个数组中取数字,使得取得的数字和最大,并且取得数字中不能是相邻的两个。

动态规划:

  1. 状态表示:$f[i]$表示前i个数的中取数得到的最大值
  2. 状态计算:
    1. 集合划分:以当前数字nums[i]是否包含进行划分,分为包含与不包含两类
    2. 状态计算:
      • 包含nums[i]: 说明nums[i-1]不能取,即f[i] = f[i - 2] + nums[i]
      • 不包含nums[i]: 为了使得综合最大,nums[i-1]一定会取即f[i] = f[i - 1]
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(!n) return 0;
        if(n==1) return nums[0];

        vector<int> f(n);
        f[0] = nums[0];
        f[1] = max(nums[1], nums[0]);
        for(int i = 2; i < n; i++)
            f[i] = max(f[i - 2] + nums[i], f[i - 1]);

        return f[n-1];
    }
};


打家劫舍II(213)



题目分析:

打家劫舍II相比与第一题就是多了一个条件,最后一家又回到了第一家,形成了一个环。这一题只需要考虑第一家或者第二家的是否取的问题,不需要考虑取完最后一家还可以继续重新来一遍,因为前面已经按照间隔取过一次了,第二次遍历的话没取过的旁边肯定是已经取过了的,所以不能再走一遍

动态规划:

这里的具体分析与第一题是完全一样的,只是需要分别讨论刚开始取第一个数还是最后一次取第一个数的问题,其实还有一种情况就是第一次和最后一次都不取,但是实际可以发现,不取第一个数的情况久包括了前后都不取。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(!n) return 0;
        if(n == 1) return nums[0];

        vector<int> f(n);
        int ans = 0;
        // 取第一个数
        f[0] = nums[0];
        f[1] = max(nums[0], nums[1]);
        for(int i = 2; i < n - 1; i ++)
            f[i] = max(f[i - 2] + nums[i], f[i - 1]);
        ans = max(ans, f[n - 2]);

        // 不取第一个数
        f[0] = 0;
        f[1] = nums[1];
        for(int i = 2; i < n; i ++)
            f[i] = max(f[i - 2] + nums[i], f[i - 1]);

        return max(ans, f[n - 1]);
    }
};