動機

超有意思的題目，只能用bottomup dp的題目!! 下次不能說topdown與bottomup的dp可以互換了

  • topdown dp與bottomup dp差在一個在前半段處理，另一個在後半段

因為上面的特質導致這題只能用bottomup

Problem

Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.

 

Example 1:

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]Output: 3Explanation: The repeated subarray with maximum length is [3,2,1].

Example 2:

Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]Output: 5

 

Constraints:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 100

Sol

因為需要追蹤長度，所以一定會多一個維度去看長度，就會變成三維

但如果用bottomup就會在bottomup時順便把長度算好，變成只要看二維就好!!

class Solution:
    def findLength(self, ns1: List[int], ns2: List[int]) -> int:
        '''
        @cache
        def dp(i,j,k):
            if i < 0 or j < 0:
                return k

            if ns1[i] == ns2[j]:
                ret = dp(i-1,j-1,k+1)
            else:
                ret = k
            return max(ret, dp(i-1,j,0), dp(i,j-1,0))
        
        return dp(len(ns1)-1,len(ns2)-1,0)
        '''
        
        dp = [[0] * (len(ns2)) for _ in range(len(ns1))]
        ret = 0
        for i in range(1,len(ns1)):
            for j in range(1,len(ns2)):
                if ns1[i] == ns2[j]:
                    dp[i][j] = dp[i-1][j-1]+1
                    ret = max(ret, dp[i][j])
        return ret