写在前面
难度：中等动态规划
动态规划（Dynamic Programming，DP）求解问题一般具有以下3个性质：
最优子结构边界状态转移公式 示例说明
F(n) = F(n-1) + F(n-2)(n >= 3);
F(2) = 2;
F(1) = 1;
称F(2)和F(1)是问题的"边界"
状态转移公式：F(n) = F(n-1) + F(n-2)
题目详情
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例 1:
输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释:
长度最长的公共子数组是 [3, 2, 1]。
说明:
1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100
ac代码
示例矩阵
A: [1,2,3,2,1]B: [3,2,1,4,7]清晰明了，不再赘述（1图 / 表胜千言）
A\B空串32147空串00000010001002001000301000020020001000300
class Solution
{
public:
int findLength(vector<int>& A, vector<int>& B)
{
int dp[1001][1001];
for(int i=0; i<=B.size(); i++)
dp[0][i]=0;
for(int i=0; i<=A.size(); i++)
dp[i][0]=0;
int ans = 0;
for(int i=1; i<=A.size(); i++)
{
for(int j=1; j<=B.size(); j++)
{
if(A[i-1]==B[j-1])
{
dp[i][j] = dp[i-1][j-1]+1;
ans = max(ans,dp[i][j]);
}
else
dp[i][j] = 0;
}
}
return ans;
}
};
参考文章
LeetCode 718.最长重复子数组[leetcode]718. 最长重复子数组(Maximum Length of Repeated Subarray)
Processed:
0.018, SQL:
9
