题解 | #最长公共子数组#
最长公共子数组
http://www.nowcoder.com/practice/6032826d387c4a10ad3690cce5fdb015
题意：
给定两个整数数组，求两个数组的最长的公共子数组的长度。
方法一：
动态规划
思路：dp[i][j]表示数组A以A[i]结尾，数组B以B[j]结尾公共子数组的长度。状态转移方程：if(A[i-1]==B[j-1]){//如果相等，则+1 dp[i][j]=dp[i-1][j-1]+1; }else{//否则，置为0 dp[i][j]=0; }
class Solution {
public:
int dp[1005][1005]={0};//dp[i][j]表示数组A以A[i]结尾，数组B以B[j]结尾公共子数组的长度
int longestCommonSubarry(vector<int>& A, vector<int>& B) {
int n=A.size(),m=B.size();
int res=0;
for(int i=1;i<=n;i++){//二重循环
for(int j=1;j<=m;j++){
if(A[i-1]==B[j-1]){//如果相等，则+1
dp[i][j]=dp[i-1][j-1]+1;
}else{//否则，置为0
dp[i][j]=0;
}
res=max(res,dp[i][j]);//维护最大值
}
}
return res;
}
};
时间复杂度：%2C%E4%BA%8C%E9%87%8D%E5%BE%AA%E7%8E%AF%E9%81%8D%E5%8E%86%E3%80%82)
空间复杂度：%2C%E5%AD%98%E5%82%A8dp%E6%95%B0%E7%BB%84%E3%80%82)
方法二：
java实现
思路：思路同方法一相同，根据状态转移方程实现。
import java.util.*;
public class Solution {
int[][] dp=new int[1005][1005];//dp[i][j]表示数组A以A[i]结尾，数组B以B[j]结尾公共子数组的长度
public int longestCommonSubarry (int[] A, int[] B) {
int n=A.length,m=B.length;
int res=0;
for(int i=1;i<=n;i++){//二重循环
for(int j=1;j<=m;j++){
if(A[i-1]==B[j-1]){//如果相等，则+1
dp[i][j]=dp[i-1][j-1]+1;
}else{//否则，置为0
dp[i][j]=0;
}
res=Math.max(res,dp[i][j]);//维护最大值
}
}
return res;
}
}
时间复杂度：空间复杂度：
