C++动态规划dp算法题(2)

如上的实现复杂度为N方,可以增加归纳的假设,增加b[k]存储长度为k最长子序列最小结尾元素,那么可以利用二分查找,使用logn查找到插入点,对于每次比较,要么直接比较b【k】比它大直接k+1,更新b【k+1】,要么二分查找到位置,更新b【j】,所以最终复杂度为nlogn(如果数据量大的话,使用该算法较好)

C++动态规划dp算法题

问题5:最长公共子序列长度(LCS)

C++动态规划dp算法题

上图可以看出使用了斜侧的比较,所以不能再使用1维数组了

class LCS {
public:
    int findLCS(string A, int n, string B, int m) {
        if (A.empty()||n==0||B.empty()||m==0)
            return 0;
        vector<vector<int> > dp(n,vector<int>(m));
        //下面是两个for的初始化,当出现第一个相等的时,后面的都直接赋值为1;
        for (int i = 0;i < m;i++) {
            if (A[0] == B[i]) {
                for (int j = i;j < m;j++)
                    dp[0][j] = 1;
                break ;
            }             
        }
        for (int i = 0;i < n;i++) {
            if (B[0] == A[i]) {
                for (int j = i;j < n;j++)
                    dp[j][0] = 1;
                break ;
            }             
        }
        for (int i = 1;i < n;i++) {
            for (int j = 1;j < m;j++) {
                if (A[i] == B[j])
                    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-1][m-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; //第1行也可以照此直接初始化
                }
                else {
                    dp[i][j] = max( dp[i-1][j] ,dp[i][j-1]);
                }               
            }
        }
        return dp[n][m];
    }
};

问题6:背包

N件物品,价值记录在数组V,重量记录在数组W,背包总重量最大为cap,要求总价值最大;

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/284f6f9932e32df11f1717bef4831ca6.html