关于动态规划【力扣718.最长重复子数组的思考】

📅 2026/7/3 19:31:28
关于动态规划【力扣718.最长重复子数组的思考】
1、为什么dp数组要定义为二维数组// dp数组定义为二维是因为最长重复子数组的长度会受到两个东西的影响1、nums1数组的元素值2、nums2数组的元素值。// 如果nums1和nums2在某个地方的值一样连续下去的值也一样就会影响重复的长度。// 所以dp数组定义为二维dp数组的定义如下图所示2、为什么dp数组的定义有1001// 因为题目的提示有提到nums1和nums2的长度不超过1001二维数组的定义用的是C语法3、为什么dp[i][j]要表示以数组下标i-1结尾的nums1数组和以数组下标j-1为结尾的...而不是以数组下标i结尾的nums1数组和以数组下标j为结尾的...// 是为了方便后续的数组初始化// 如果dp[i][j]表示以数组下标i结尾的nums1数组和以数组下标j为结尾的最长重复子数组长度为dp[i][j]那么在初始化二维数组的第一行dp[0][j]和第一列dp[i][0]的时候要单独用两次for循环去计算如果dp[0][0]和dp[0][j]相等的时候把dp[0][j]赋值为1表示重复的长度为1如果dp[0][0]和dp[i][0]相等的时候把dp[i][0]赋值为1表示重复的长度为1。// 但是如果用dp[i][j]表示以数组下标i-1结尾的nums1数组和以数组下标j-1为结尾的最长重复子数组长度为dp[i][j]那么在初始化二维数组的第一行dp[0][j]和第一列dp[i][0]的时候就直接交给递推公式了// 所以这里dp[i][j]要表示以数组下标i-1结尾的nums1数组和以数组下标j-1为结尾的...(省略号处为最长重复子数组长度为dp[i][j])...