---
# System prepended metadata

title: 1458. Max Dot Product of Two Subsequences
tags: [Leetcode, Dynamic Programming, Hard]

---

# 1458. Max Dot Product of Two Subsequences
###### tags: `Leetcode` `Dynamic Programming` `Hard`
Link: https://leetcode.com/problems/max-dot-product-of-two-subsequences/
## 思路
```dp[i][j]```表示```nums1```前```i```个元素和```nums2```前```j```个元素的max dot product of two sequences
所以分两种情况:
1. ```nums1[i]```和```nums2[j]```组成一对 那么```dp[i][j] = dp[i-1][j-1]+A[i]*B[j]``` 注意，当```dp[i-1][j-1]<0```时，该项其实应该略去，即```dp[i][j] = A[i]*B[j]```
2. ```nums1[i]```和```nums2[j]```不组成一对 那么这两个元素必然至少有一个不会被用来参与点乘。所以```dp[i][j] = max{dp[i-1][j], dp[i][j-1]}```

要注意之前遇到这种题我们会考虑给```dp[i][0]```和```dp[0][j]```赋初始值
但这道题两个subsequence不能是empty的
所以如果我们让```dp[i][0]```,```dp[0][j]```都等于0 那么[-1,-1] [1,1]这个test case的值就会是0
所以我们要设成两个subsequence如果其中有一个是empty的就是不合法的
## Code
```java=
class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m+1][n+1];
        for(int i=0; i<=m; i++) Arrays.fill(dp[i], Integer.MIN_VALUE);
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                int sum1 = dp[i-1][j-1]>0?(dp[i-1][j-1]+nums1[i-1]*nums2[j-1]):(nums1[i-1]*nums2[j-1]);
                int sum2 = Math.max(dp[i-1][j], dp[i][j-1]);
                dp[i][j] = Math.max(sum1, sum2);
            }
        }
        return dp[m][n];
    }
}
```