首页 > 代码库 > 最长连续公共子串、最长公共子串(可以非连续)、最长回文串(连续)、最长回文串(可以不连续)、最长递增数组的求解

最长连续公共子串、最长公共子串(可以非连续)、最长回文串(连续)、最长回文串(可以不连续)、最长递增数组的求解

问题:最长连续公共子串、最长公共子串(可以非连续)、最长回文串(连续)、最长回文串(可以不连续)、最长递增数组、长方形镶嵌最多的求解

方法:上述问题有相似性,都可以采用动态规划进行求解。

(1)最长连续公共子串:

如果A[i]==B[j], dp[i][j]=dp[i-1][j-1]+1;

否则,dp[i][j]=0;

(2)最长公共子串(可非连续):

如果A[i]==B[j], dp[i][j]=dp[i-1][j-1]+1;

否则,dp[i][j]=dp[i-1][j-1];

(3)最长回文串(可非连续):

先将原字符串A逆序得到新字符串B,然后采用最长公共子串(可非连续)进行求解。

(4)最长连续回文串:

先将原字符串A逆序得到新字符串B,然后采用最长连续公共子串进行求解。

(5)最长连续递增数组:

如果A[i]>A[i-1],dp[i]=dp[i-1]+1;

否则,dp[i]=0;

(6)最长递增数组(可非连续):

如果A[i]>A[i-1],dp[i]=dp[i-1]+1;

否则,dp[i]=dp[i-1];

(7)长方形镶嵌数量:

先按照长方形的长进行升序排序(如果长一样,宽大的排后边);

如果A[i].length>A[i-1].length且A[i].width>A[i-1].width,则dp[i]=dp[i-1]+1;

否则,dp[i]=dp[i-1];

最长连续公共子串、最长公共子串(可以非连续)、最长回文串(连续)、最长回文串(可以不连续)、最长递增数组的求解