题目大意：
两个子序列的最大点积
给你两个数组 nums1 和 nums2 。
请你返回 nums1 和 nums2 中两个长度相同的 非空 子序列的最大点积。
数组的非空子序列是通过删除原数组中某些元素（可能一个也不删除）后剩余数字组成的序列，但不能改变数字间相对顺序。比方说，[2,3,5] 是 [1,2,3,4,5] 的一个子序列而 [1,5,3] 不是。
示例 1：
输入：nums1 = [2,1,-2,5], nums2 = [3,0,-6] 输出：18 解释：从 nums1 中得到子序列 [2,-2] ，从 nums2 中得到子序列 [3,-6] 。 它们的点积为 (23 + (-2)(-6)) = 18 。
示例 2：
输入：nums1 = [3,-2], nums2 = [2,-6,7] 输出：21 解释：从 nums1 中得到子序列 [3] ，从 nums2 中得到子序列 [7] 。 它们的点积为 (3*7) = 21 。
示例 3：
输入：nums1 = [-1,-1], nums2 = [1,1] 输出：-1 解释：从 nums1 中得到子序列 [-1] ，从 nums2 中得到子序列 [1] 。 它们的点积为 -1 。
提示：
1 <= nums1.length, nums2.length <= 500-1000 <= nums1[i], nums2[i] <= 100
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1458
解题思路分析：
每次遇到这种动态规划的题目时，我都会想起电影骇客帝国中先知的一句名言「问题的关键在于选择」。本题的关键也在于选择，对于这种从1个或者几个数组中找出符合条件子串或者子序列并求最值的问题，由于选择的方案众多并且很难一下子判断出最值，因此我们通常会考虑使用动态规划（DP）来解题。通常情况下所有的DP问题都可以使用递归加记忆数组的方式来替代，我个人认为后者更加便于理解因此做题时更倾向于使用递归方式来解题，本题也不例外。
由于选择的方案很多，因此我们从两个数组第0位开始向后逐一尝试，我们定义两个数组的下标分别为i1和i2，并设置当前递归中的最大点积为max。对于当前的i1和i2我们有5种选择：
- 选择i1和i2。此时点积为nums1[i1] * nums2[i2]，并使用该点积更新全局最大值max。不再继续选择其他数字。
- 选择i1和i2并得到了点积nums1[i1] * nums2[i2]后，我们继续选择其他数字，此时由于i1和i2已经被选择过，因此我们需要将其下标分别加一，递归至子问题继续从后面的下标中选择数字，子问题的结果加上当前的点积为一个新的结果，并利用该结果更新最大值max。
- 不选择当前i1和i2，直接将其下标分别加一，递归至子问题得到一个新的结果，并利用该结果更新最大值max。
- 只选择i1，并将i1加一递归至子问题，利用子问题结果更新最大值max。
- 只选择i2，并将i2加一递归至子问题，利用子问题结果更新最大值max。
使用代码来描述上述逻辑即是：
max = nums1[i1] * nums2[i2]; max = max(max, nums1[i1] * nums2[i2]+help(i1+1,i2+1)); max = max(max, help(i1+1,i2+1)); max = max(max, help(i1+1,i2)); max = max(max, help(i1,i2+1));
我们比骇客帝国中的救世主更幸运的是，我们可以在尝试做出所有选择后，找到一个最优解来解决当前问题，因此上述的max值为当前递归的最优返回值。
接下来再考虑记忆数组（相当于动态规划中的DP数组）。由于递归函数中存在2个可变参数i1和i2，因此记忆数组需要定义一个2维数组来记录i1和i2变化时对应的结果。
实现代码：
Integer[][] memo; // 记忆数组
public int maxDotProduct(int[] nums1, int[] nums2) {
// 初始化记忆数组
memo=new Integer[nums1.length][nums2.length];
// 递归求解
return help(nums1,nums2,0,0);
}
int help(int[] nums1, int[] nums2, int i1, int i2){
// 如果记忆数组中存在当前解，直接返回
if(memo[i1][i2]!=null) return memo[i1][i2];
// 第一种情况，最大值为当前两数乘积
int max=nums1[i1]*nums2[i2];
if(i1+1<nums1.length&&i2+1<nums2.length){
// 将两个数字下标分别加一递归至子问题
int res=help(nums1,nums2,i1+1,i2+1);
max=Math.max(max, max+res); // 选择当前2个数字后的点积
max=Math.max(max, res); // 不选择当前2个数字后的点积
}
if(i2+1<nums2.length){
// 只选择i2后的点积
max=Math.max(max, help(nums1,nums2,i1,i2+1));
}
if(i1+1<nums1.length){
// 只选择i1后的点积
max=Math.max(max, help(nums1,nums2,i1+1,i2));
}
memo[i1][i2]=max; // 将max存入记忆数组
return max;
}本题解法执行时间为12ms。
Runtime: 12 ms, faster than 50.00% of Java online submissions for Max Dot Product of Two Subsequences.
Memory Usage: 42.8 MB, less than 100.00% of Java online submissions for Max Dot Product of Two Subsequences.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1458-max-dot-product-of-two-subsequences-解题思路分析/