# 1458. Max Dot Product of Two Subsequences
###### tags: `Leetcode` `Dynamic Programming` `Hard`
Link: https://leetcode.com/problems/max-dot-product-of-two-subsequences/
## 思路

所以分两种情况:
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

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];
}
}