东哥经典动态规划

发表于 | 分类于 ， ， |

labuladong 的经典动态规划题

53.最大子数组和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n);
        //base case
        dp[0]=nums[0];

        for(int i=1;i<n;i++){
            dp[i]=max(dp[i-1]+nums[i], nums[i]);
        }
        int res=INT_MIN;
        for(int i=0;i<n;i++){
            res = max(res, dp[i]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func maxSubArray(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    //base case
    dp[0] = nums[0]

    for i := 1; i < n; i++ {
        dp[i] = max(dp[i-1]+nums[i], nums[i])
    }
    res := math.MinInt32
    for i := 0; i < n; i++ {
        res = max(res, dp[i])
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

1800.最大升序子数组和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int maxAscendingSum(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n);

        //base case
        dp[0]=nums[0];

        for(int i=1;i<n;i++){
            if(nums[i]>nums[i-1]){
                dp[i]=max(dp[i-1]+nums[i], nums[i]);
            }else{
                dp[i]=nums[i];
            }
        }
        int res=INT_MIN;
        for(int i=0;i<n;i++){
            res = max(res, dp[i]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func maxAscendingSum(nums []int) int {
    n := len(nums)
    dp := make([]int, n)

    //base case
    dp[0] = nums[0]

    for i := 1; i < n; i++ {
        if nums[i] > nums[i-1] {
            dp[i] = max(dp[i-1]+nums[i], nums[i])
        } else {
            dp[i] = nums[i]
        }
    }
    res := math.MinInt32
    for i := 0; i < n; i++ {
        res = max(res, dp[i])
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

1186.删除一次得到子数组最大和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int maximumSum(vector<int>& arr) {
        int n=arr.size();
        int res=INT_MIN;

        //dp0[i]代表以arr[i]为结尾的最大连续子数组和
        vector<int> dp0(n);  
        //dp1[i]代表以arr[i]为结尾的并且删除了一个元素（可能是arr[i]自己）后最大的连续子数组和
        vector<int> dp1(n); 

        //base case
        dp0[0]=arr[0];
        dp1[0]=arr[0]; //因为删除元素后不能为空，所以dp1[0]=arr[0];

        for(int i=1;i<n;i++){
            dp0[i]=max(dp0[i-1]+arr[i], arr[i]);
            dp1[i]=max(dp0[i-1], dp1[i-1]+arr[i]);
        }

        for(int i=0;i<n;i++){
            res = max(dp0[i], res);
            res = max(dp1[i], res);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func maximumSum(arr []int) int {
    n := len(arr)
    res := math.MinInt32

    //dp0[i]代表以arr[i]为结尾的最大连续子数组和
    dp0 := make([]int, n)
    //dp1[i]代表以arr[i]为结尾的并且删除了一个元素（可能是arr[i]自己）后最大的连续子数组和
    dp1 := make([]int, n)

    //base case
    dp0[0] = arr[0]
    dp1[0] = arr[0] //因为删除元素后不能为空，所以dp1[0]=arr[0];

    for i := 1; i < n; i++ {
        dp0[i] = max(dp0[i-1]+arr[i], arr[i])
        dp1[i] = max(dp0[i-1], dp1[i-1]+arr[i])
    }

    for i := 0; i < n; i++ {
        res = max(dp0[i], res)
        res = max(dp1[i], res)
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

152.乘积最大子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n=nums.size();

        //dp_min[i] 以 nums[i] 结尾的连续子数组的乘积的最小值
        //dp_max[i] 以 nums[i] 结尾的连续子数组的乘积的最大值

        vector<int> dp_min(n);
        vector<int> dp_max(n);
        
        //base case
        dp_max[0]=nums[0];
        dp_min[0]=nums[0];

        for(int i=1;i<n;i++){
            if(nums[i]>=0){
                dp_max[i]=max(dp_max[i-1]*nums[i], nums[i]);
                dp_min[i]=min(dp_min[i-1]*nums[i], nums[i]);
            }else{
                dp_max[i]=max(dp_min[i-1]*nums[i], nums[i]);
                dp_min[i]=min(dp_max[i-1]*nums[i], nums[i]);
            }
        }
        int res=INT_MIN;
        for(int i=0;i<n;i++){
            res = max(res, dp_max[i]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
func maxProduct(nums []int) int {
    n := len(nums)

    //dp_min[i] 以 nums[i] 结尾的连续子数组的乘积的最小值
    //dp_max[i] 以 nums[i] 结尾的连续子数组的乘积的最大值

    dp_min := make([]int, n)
    dp_max := make([]int, n)
    
    //base case
    dp_max[0] = nums[0]
    dp_min[0] = nums[0]

    for i := 1; i < n; i++ {
        if nums[i] >= 0 {
            dp_max[i] = max(dp_max[i-1]*nums[i], nums[i])
            dp_min[i] = min(dp_min[i-1]*nums[i], nums[i])
        } else {
            dp_max[i] = max(dp_min[i-1]*nums[i], nums[i])
            dp_min[i] = min(dp_max[i-1]*nums[i], nums[i])
        }
    }
    res := math.MinInt32
    for i := 0; i < n; i++ {
        res = max(res, dp_max[i])
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

64.最小路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        //动态规划
        int m=grid.size();
        int n=grid[0].size();
        vector<vector<int>> dp(m,vector<int>(n));

        //base case
        dp[0][0]=grid[0][0];
        for(int i=1;i<m;i++){
            dp[i][0]=dp[i-1][0]+grid[i][0];
        }
        for(int i=1;i<n;i++){
            dp[0][i]=dp[0][i-1]+grid[0][i];
        }

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=min(dp[i-1][j], dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func minPathSum(grid [][]int) int {
    //动态规划
    m := len(grid)
    n := len(grid[0])
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    //base case
    dp[0][0] = grid[0][0]
    for i := 1; i < m; i++ {
        dp[i][0] = dp[i-1][0] + grid[i][0]
    }
    for i := 1; i < n; i++ {
        dp[0][i] = dp[0][i-1] + grid[0][i]
    }

    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        }
    }
    return dp[m-1][n-1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

72.编辑距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int minDistance(string word1, string word2) {
        //word1[0..i] 和 word2[0..j] 的最小编辑距离是 dp[i][j]
        int m=word1.size();
        int n=word2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));

        //base case
        for(int i=1;i<=m;i++){
            dp[i][0]=i;
        }

        for(int j=1;j<=n;j++){
            dp[0][j]=j;
        }

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(word1[i-1]==word2[j-1]){
                    dp[i][j]=dp[i-1][j-1];    //什么都不做
                }else{
                    //dp[i-1][j] 删除，dp[i][j-1]插入，dp[i-1][j-1]替换
                    dp[i][j]=min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1])+1;
                }
            }
        }
        return dp[m][n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
func minDistance(word1 string, word2 string) int {
    //word1[0..i] 和 word2[0..j] 的最小编辑距离是 dp[i][j]
    m := len(word1)
    n := len(word2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    //base case
    for i := 1; i <= m; i++ {
        dp[i][0] = i
    }

    for j := 1; j <= n; j++ {
        dp[0][j] = j
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]    //什么都不做
            } else {
                //dp[i-1][j] 删除，dp[i][j-1]插入，dp[i-1][j-1]替换
                dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1
            }
        }
    }
    return dp[m][n]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

300.最长递增子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        //dp[i]表示以nums[i]结尾的最长递增子序列的长度
        int n=nums.size();
        vector<int> dp(n, 1);

        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                //寻找nums[0...j-1]中比nums[i]小的元素
                if(nums[i]>nums[j]){
                    //把nums[i]接在后面，形成长度为dp[j]+1，且以nums[i]为结尾的递增子序列
                    dp[i]=max(dp[i], dp[j]+1);
                }
            }
        }
        int res=0;
        for(int i=0;i<n;i++){
            res = max(res, dp[i]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func lengthOfLIS(nums []int) int {
    //dp[i]表示以nums[i]结尾的最长递增子序列的长度
    n := len(nums)
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }

    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            //寻找nums[0...j-1]中比nums[i]小的元素
            if nums[i] > nums[j] {
                //把nums[i]接在后面，形成长度为dp[j]+1，且以nums[i]为结尾的递增子序列
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
    }
    res := 0
    for i := 0; i < n; i++ {
        res = max(res, dp[i])
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

354.俄罗斯套娃信封问题

这道题目是最长递增子序列的一个变种，相当于在二维平面中找一个最长递增子序列，其长度就是最多能嵌套的信封个数。

思路：先对宽w进行升序排序，如果遇到w相等，则按照高度h降序排序；之后把所有的h作为一个数组，在这个数组上计算最长递增子序列的长度就是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    static bool Cmp(vector<int>& a, vector<int>& b){
        if(a[0]==b[0]){
            return a[1]>b[1];
        }
        return a[0]<b[0];
    }
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        //按照 w 升序排列，如果 w 相等，则按照 h 降序排列
        sort(envelopes.begin(), envelopes.end(), Cmp);
        int n=envelopes.size();
        vector<int> nums(n);
        for(int i=0;i<n;i++){
            nums[i]=envelopes[i][1];
        }
        int res = LIS(nums);
        return res;
    }
    //最长递增子序列
    int LIS(vector<int>& nums){
        int n=nums.size();
        vector<int> dp(n, 1);

        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i]=max(dp[i], dp[j]+1);
                }
            }
        }
        int res=0;
        for(int i=0;i<n;i++){
            res=max(res, dp[i]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
func maxEnvelopes(envelopes [][]int) int {
    //按照 w 升序排列，如果 w 相等，则按照 h 降序排列
    sort.Slice(envelopes, func(i, j int) bool {
        if envelopes[i][0] == envelopes[j][0] {
            return envelopes[i][1] > envelopes[j][1]
        }
        return envelopes[i][0] < envelopes[j][0]
    })
    
    n := len(envelopes)
    nums := make([]int, n)
    for i := 0; i < n; i++ {
        nums[i] = envelopes[i][1]
    }
    res := LIS(nums)
    return res
}

//最长递增子序列
func LIS(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }

    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
    }
    res := 0
    for i := 0; i < n; i++ {
        res = max(res, dp[i])
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

673.最长递增子序列的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n, 1); //以nums[i]结尾的最长上升子序列的长度
        vector<int> count(n, 1); //以nums[i]结尾的最长上升子序列的个数

        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    if(dp[j]+1 > dp[i]){
                        count[i] = count[j];
                    }else if(dp[j]+1 == dp[i]){
                        count[i] +=count[j];
                    }
                    dp[i]=max(dp[i], dp[j]+1);
                }
            }
        }

        int res = 0;
        for(int i=0;i<n;i++){
            res=max(res, dp[i]);
        }

        int result = 0;
        for(int i=0;i<n;i++){
            if(dp[i]==res) result += count[i];
        }
        
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
func findNumberOfLIS(nums []int) int {
    n := len(nums)
    dp := make([]int, n)    //以nums[i]结尾的最长上升子序列的长度
    count := make([]int, n) //以nums[i]结尾的最长上升子序列的个数
    
    for i := range dp {
        dp[i] = 1
        count[i] = 1
    }

    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                if dp[j]+1 > dp[i] {
                    count[i] = count[j]
                } else if dp[j]+1 == dp[i] {
                    count[i] += count[j]
                }
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
    }

    res := 0
    for i := 0; i < n; i++ {
        res = max(res, dp[i])
    }

    result := 0
    for i := 0; i < n; i++ {
        if dp[i] == res {
            result += count[i]
        }
    }
    
    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

1143.最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m=text1.size();
        int n=text2.size();
        //定义：对于text1[0...i-1] 和 text2[0...j-1]，的最长公共子序列为 dp[i][j]
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(text1[i-1]==text2[j-1]){
                    //找到一个lcs中的元素
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    //至少有一个字符不在 lcs 中
                    dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func longestCommonSubsequence(text1 string, text2 string) int {
    m := len(text1)
    n := len(text2)
    //定义：对于text1[0...i-1] 和 text2[0...j-1]，的最长公共子序列为 dp[i][j]
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                //找到一个lcs中的元素
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                //至少有一个字符不在 lcs 中
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[m][n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

583.两个字符串的删除操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int minDistance(string word1, string word2) {
        //删除之后的结果，就是最长公共子序列;
        int m=word1.size();
        int n=word2.size();
        
        return m+n-2*LCS(word1, word2);
    }
    int LCS(string s1, string s2){
        int m=s1.size();
        int n=s2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(s1[i-1]==s2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func minDistance(word1 string, word2 string) int {
    //删除之后的结果，就是最长公共子序列;
    m := len(word1)
    n := len(word2)
    
    return m + n - 2*LCS(word1, word2)
}

func LCS(s1 string, s2 string) int {
    m := len(s1)
    n := len(s2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if s1[i-1] == s2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[m][n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

712.两个字符串的最小ASCII删除和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m=s1.size(); 
        int n=s2.size();
        //dp[i][j]代表s1[:i]和s2[:j]的最小删除和
        vector<vector<int>> dp(m+1,vector<int>(n+1, 0));

        //base case;
        for(int i=1;i<=m;i++){
            dp[i][0]=dp[i-1][0]+s1[i-1];
        }
        for(int j=1;j<=n;j++){
            dp[0][j]=dp[0][j-1]+s2[j-1];
        }

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(s1[i-1]==s2[j-1]){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=min(dp[i-1][j]+s1[i-1], dp[i][j-1]+s2[j-1]);
                }
            }
        }
        return dp[m][n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func minimumDeleteSum(s1 string, s2 string) int {
    m := len(s1)
    n := len(s2)
    //dp[i][j]代表s1[:i]和s2[:j]的最小删除和
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    //base case;
    for i := 1; i <= m; i++ {
        dp[i][0] = dp[i-1][0] + int(s1[i-1])
    }
    for j := 1; j <= n; j++ {
        dp[0][j] = dp[0][j-1] + int(s2[j-1])
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if s1[i-1] == s2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = min(dp[i-1][j]+int(s1[i-1]), dp[i][j-1]+int(s2[j-1]))
            }
        }
    }
    return dp[m][n]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

718.最长重复子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        //动态规划：dp[i][j]表示 nums1[0...i-1]和nums2[0...j-1]结尾的最长重复子数组
        int m=nums1.size();
        int n=nums2.size();
        int res = INT_MIN;
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(nums1[i-1]==nums2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                res = max(res, dp[i][j]);
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func findLength(nums1 []int, nums2 []int) int {
    //动态规划：dp[i][j]表示 nums1[0...i-1]和nums2[0...j-1]结尾的最长重复子数组
    m := len(nums1)
    n := len(nums2)
    res := math.MinInt32
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if nums1[i-1] == nums2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            }
            res = max(res, dp[i][j])
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
-------------本文结束 感谢阅读-------------
0%