算法——最长重复子数组（动态规划）

给两个整数数组nums1和nums2，返回两个数组中公共的、长度最长的子数组的长度。

. – 力扣（LeetCode）

方法：动态规划.

dp[i][j] 表示，第一个数组的索引i与第二个数组索引j所在位置的元素，从两个数组该位置开始一直到最后相同元素的最大长度。显然如果该位置二者不相等则dp数组值为0.若相等，则weidp[i+1][j+1]+1，即该位置相等，至少为1，加上二者后一个位置的最大长度。这就是状态转移方程。

官方代码一如既往的精简。

在申请数组时多申请一行一列，且赋值为零，在正常范围内计算时如果需要加上也是加上零，无影响。代码精炼，赞。

在涉及到边界条件且与内部情况不一致时，可以添加外层边界，让边界参与同样的计算。（链表增加虚拟头结点也是这样的原理）

class Solution {
public:
    int findLength(vector& A, vector& B) {
        int n = A.size(), m = B.size();
        vector> dp(n + 1, vector(m + 1, 0));
        int ans = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0;
                ans = max(ans, dp[i][j]);
            }
        }
        return ans;
    }
};

附上菜鸡自己的：（原来二维vector数组也是可以直接初始化的）

class Solution {
public:
    int findLength(vector& nums1, vector& nums2) {
        vector>dp(nums1.size());
        int maxlen=INT_MIN;
        for(int i=0;i=0;i--)
        {
            for(int j=nums2.size()-2;j>=0;j--)
       服务器托管网     {
                if(nums1[i]=服务器托管网=nums2[j])
                {
                    dp[i][j]=dp[i+1][j+1]+1;
                    maxlen=max(maxlen,dp[i][j]);
                }
                else
                {
                    dp[i][j]=0;
                    maxlen=max(maxlen,dp[i][j]);
                }
            }
        }
        return maxlen;
    }
};

附：可降维优化为一维dp数组。（未尝试）

降维优化
dp[i][j] 只依赖上一行上一列的对角线的值，所以我们从右上角开始计算。
一维数组 dp ， dp[j] 是以 A[i-1], B[j-1] 为末尾项的最长公共子数组的长度

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: 如何解决缓存和数据库的数据不一致问题

数据不一致问题是操作数据库和操作缓存值的过程中，其中一个操作失败的情况。实际上，即使这两个操作第一次执行时都没有失败，当有大量并发请求时，应用还是有可能读到不一致的数据。 如何更新缓存 更新缓存的步骤就两步，更新缓存和更新数据库。但是这两步会引申多种情况。 先…