题目描述
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例：
输入： 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
思路：
DP 思路：
单看 A 、B数组的最后一项，如果它们俩不一样，公共子序列不包括它们俩—— 以它们俩为末尾项形成不了公共子序列：dp[i][j] = 0如果他们俩一样，则要考虑它们俩前面的序列【能为它们俩提供多大的公共长度】dp[i-1][j-1]它们俩的前缀序列的【最后一项】不相同，即它们的前一项不相同，由于子数组的连续性，前缀序列不能为它们俩提供公共长度 dp[i][j] = 0 + 1 = 1它们俩的前缀序列的【最后一项】相同，则可以为它们俩提供公共长度 dp[i][j] = dp[i-1][j-1] + 1 图来源自leetcode作者：hyj8
代码：
class Solution {
public:
int findLength(vector
<int>& A
, vector
<int>& B
) {
int dp
[A
.size()][B
.size()];
int max
= 0;
for(int c
= 0; c
<A
.size();c
++){
for(int r
= 0;r
<B
.size();r
++){
dp
[c
][r
] = 0;
}
}
for(int r
= 0;r
<A
.size();r
++){
for(int c
= 0;c
<B
.size();c
++){
if(A
[r
] == B
[c
] ){
if(r
== 0 || c
== 0)
{
dp
[c
][r
] = 1;
}
else{
dp
[c
][r
] = dp
[c
-1][r
-1] + 1;
}
}
if(dp
[c
][r
] > max
) {
max
= dp
[c
][r
];
}
}
}
return max
;
}
};
时间复杂度 O(n^2)，即 O(n * m)。 空间复杂度 O(n * m)
总结：
动态规划的核心思想是把原问题分解成子问题进行求解，还是分治的思想。抽象出子问题然后找到子问题之间的联系，考虑好状态表示、状态转移、边界，会比较好思考出答案。
