动态规划集合

动态规划,提起来就头大┭┮﹏┭┮, 以本文记录常考的动态规划算法

在问题满足动态规划求解的时候, 动态规划主要靠维护一个数组来记录状态转移值, 只要能写出状态转移方程与合理初始化数组基本就能解了

编辑距离

给定两个字符串, 在允许对字符串进行给定操作的情况下, 将A串变为B串的最小代价. 如允许的编辑操作为插入一个字符、删除一个字符和替换一个字符.

给定字符串A=“abcd”, B=“bce”, 创建数组dp[len(A)+1,len(B)+1], 其中dp[i][j] 表示A[0:i]与B[0:j]的最小编辑距离

0 b c e 0 a b c d

初始化时, 当A串只有0个元素时到B串的编辑距离为B串的长度, 因此 dp[0][j]=j, 同理 dp[i][0]=i

0 b c e 0 0 1 2 3 a 1 b 2 c 3 d 4

当i& j >=1时, 考虑当A[i]==B[j] 时, 这两个字符不用变, 因此编辑距离为A[i-1] 与 B[j-1]的最小编辑距离. dp[i][j] = dp[i-1][j-1]. 当A[i]!=B[j]时, dp[i][j]=min(dp[i-1][j]+1, dp[i][j-1]+1， dp[i-1][j-1]+1). dp[i][j-1] + 1 表示将长为i转换为j-1的编辑距离再加一, 1为删除的操作. dp[i-1][j] + 1 表示长度i-1转换为j的编辑距离, 1为插入的操作

int edit_distance(vector<char> str1, vector<char> str2){
    int len1 = str1.size();
    int len2 = str2.size();
    if(len1==0 || len2==0)
        return max(len1, len2);
    vector<vector<int>> dp(len1+1, vector<int>(len2+1, 0));
    for(int i=0; i<=len1; i++)
        dp[i][0]=i;
    for(int j=0; j<=len2;j++)
        dp[0][j]=j;
    for(int i=1; i<=len1; i++)
        for(int j=1;j<=len2; j++){
            if(str1[i-1]==str2[j-1]) // 此时字符串index为i-1, j-1
                dp[i][j] = dp[i-1][j-1];
            else{
                dp[i][j] = min(dp[i-1][j-1]+1,min(dp[i][j-1] +1, dp[i-1][j]+1));
            }
        }
    return dp[len1][len2];
}

最长公共子序列

给定两个字符串, 求出两者最长公共子序列, 子序列是指出现顺序相同但可以不连续. 如串A=abcdtfgd, B=abedifg, 最长公共子序列为abdfg

构造dp表 dp[len(A)+1][len(B)+1], dp[i][j]表示串A[0:i]与串B[0:j]的最长公共子序列. 当A[i]==B[j]时, dp[i][j]为A[0:i-1]与B[0:j-1]的最长公共子序列长度加上1. 否则, dp[i][j]为（A[0:i-1]与B[0:j]）和 （A[0:i]与B[0:j-1]）中的最长公共子序列的最大值.

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int len1 = text1.size();
        int len2 = text2.size();
        if(len1==0 || len2==0)
            return 0;
        int dp[len1+1][len2+1];
        for(int i=0;i<=len1;i++)
            dp[i][0]=0;
        for(int j=0;j<=len2;j++)
            dp[0][j]=0;
        for(int i=1;i<=len1;i++)
            for(int j=1;j<=len2;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[len1][len2];
    }
};

最长回文子串

dp[i][j]为状态转移矩阵, 表示字符串以i开始以j结尾的子串是否是回文. 首先当i==j 时, 一个字符必定是回文的, j-i=1 时, 两个字符也必是回文. 当 j-i >1 时, 当 str[i] ==str[j] 时, 如果 str[i+1, j-1]是回文, 那么str[i,j] 也是回文.

string longestPS(string s){
    if(s.size()==0)
        return '';
    bool dp[s.size()][s.size()];
    int max_len=0; /记录当前最长的回文串长度
    int begin_index=0;//记录当前最长回文串开始index
    for(int i=0;i<s.size();i++)
        for(int j=0;j<i;j++){
            if(i-j< 2)
                dp[j][i]= s[i]==s[j];// 只有一个字符或两个字符时处理
            else{
                dp[j][i]=dp[j+1][i-1] && (s[i]==s[j]);
            }
            if(dp[j][i] && (i-j+1) > max_len){
                max_len = i-j+1;
                begin_index =j;
                }
            }
    return s.substr(begin_index, max_len);
}

统计连续回文子串的个数

在最长回文子串代码上个计数器即可 若要统计不重复的回文子串, 加个set判断

int countPS(string str){
    if(str.size()==0)
        return 0;
    int len = str.size();
    vector<vector<int>> dp(len, vector<int >(len, 0));
    int count=0;
    unordered_set<string> myset;
    for(int i=0; i<len; i++)
        for (int j=0; j <= i; ++j) {
            if(i -j < 2 && str[i]==str[j]){
                dp[j][i]=1;
                if(myset.find(str.substr(j, i-j+1))==myset.end()){
                    count++;
                    myset.insert(str.substr(j, i-j+1));
                }
            }
            else{
                if(dp[j+1][i-1]==1 && str[i]==str[j]){
                    dp[j][i]=1;
                    if(myset.find(str.substr(j, i-j+1))==myset.end()){
                        count++;
                        myset.insert(str.substr(j, i-j+1));
                    }
                }
            }
        }
    return count;
}

0-1 背包问题

题目：有一个容量为 V 的背包，和一些物品。这些物品分别有两个属性，体积 w 和价值 v，每种物品只有一个。要求用这个背包装下价值尽可能多的物品，求该最大价值，背包可以不被装满

步骤1-找子问题：子问题必然是和物品有关的，对于每一个物品，有两种结果：能装下或者不能装下。第一，包的容量比物品体积小，装不下，这时的最大价值和前i-1个物品的最大价值是一样的。第二，还有足够的容量装下该物品，但是装了不一定大于当前相同体积的最优价值，所以要进行比较。由上述分析，子问题中物品数和背包容量都应当作为变量。因此子问题确定为背包容量为j时，求前i个物品所能达到最大价值。

步骤2-确定状态：由上述分析，“状态”对应的“值”即为背包容量为j时，求前i个物品所能达到最大价值，设为dp[i][j]。初始时，dp[0][j](0<=j<=V)为0，没有物品也就没有价值。

步骤3-确定状态转移方程：由上述分析，第i个物品的体积为w,价值为v，则状态转移方程为

• j<w，dp[i][j] = dp[i-1][j] //背包装不下该物品，最大价值不变
• j>=w, dp[i][j] = max{ dp[i-1][j-list[i].w] + v, dp[i-1][j] }//和不放入该物品时同样达到该体积的最大价值比较