算法笔记之动态规划

LEETCODE 718. 最长重复子数组

问题描述：
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例 1:
输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释:
长度最长的公共子数组是 [3, 2, 1]。

解题思路：最长公共子串问题，利用动态规划，A[i:]和B[i:]的公共前缀可以由A[i+1:]和B[i+1:]推出，最后求出所有公共前缀的最大值即为最长公共子数组。

Python代码：

def findLength(self, A, B):
    dp = [[0 for _ in range(len(A))] for _ in range(len(B))]
    max_value = -1
    for i in range(len(B) - 1, -1, -1):
        for j in range(len(A) - 1, -1, -1):
            if i == len(B) - 1 or j == len(A) - 1:
                if B[i] == A[j]:
                    dp[i][j] = 1
                else:
                    dp[i][j] = 0
                
            else:
                if B[i] == A[j]:
                    dp[i][j] = dp[i + 1][j + 1] + 1
                else:
                    dp[i][j] = 0
            if dp[i][j] > max_value:
                    max_value = dp[i][j]
    return max_value