给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。
示例
输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出:3
解释:
长度最长的公共子数组是 [3, 2, 1] 。
解法一:动态规划
代码:
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
int row = A.size(),col = B.size();
vector<vector<int>> dp(row + 1,vector<int>(col+1,0));
int maximum = 0;
for(int i = row-1;i>=0;--i){
for(int j = col-1;j>=0;--j){
dp[i][j] = dp[i+1][j+1]+((A[i] == B[j])?1:0);
maximum = max(dp[i][j],maximum);
}
}
return maximum;
}
};
思路
记A[i:]为数组第i个元素到数组尾的子数组,dp[i][j]为A[i:]和B[j:]的最长公共前缀,那么所求的重复子数组就是dp[i][j]的最大值,利用递推方程
\[dp(i,j)=
\begin{cases}
dp(i+1,j+1)+1,A[i]=B[j] \\
0,A[i] \ne B[j]
\end{cases}
\]
\begin{cases}
dp(i+1,j+1)+1,A[i]=B[j] \\
0,A[i] \ne B[j]
\end{cases}
\]
dp[len(A)-1][len(B)-1]递推到dp[0][0],再求出数组中的最大值。
原文链接: https://www.cnblogs.com/Swetchine/p/13221306.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/361102
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!