leetcode-718. 最长重复子数组刷题笔记（c++）

骑猪看日落 2023-02-22 05:10 6阅读 0赞

#### 写在前面 ####

*  难度：中等
 *  `动态规划`
    
     *  `动态规划（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图 / 表胜千言）

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.]
     *  [\[leetcode\]718. 最长重复子数组(Maximum Length of Repeated Subarray)][leetcode_718. _Maximum Length of Repeated Subarray]

[LeetCode 718.]: https://blog.csdn.net/weixin_43510131/article/details/84315049
[leetcode_718. _Maximum Length of Repeated Subarray]: https://blog.csdn.net/qq_29407397/article/details/93598884