LeetCode 1458. Max Dot Product of Two Subsequences
2020-05-24 21:30:54 # leetcode # dynamic programming

Problem

LeetCode 1458. Max Dot Product of Two Subsequences

1. 题目简述

给出两个数组 nums1 和 nums2 。

请返回 nums1 和 nums2 中两个长度相同的 非空 子序列的最大点积。

数组的非空子序列是通过删除原数组中某些元素（可能一个也不删除）后剩余数字组成的序列，但不能改变数字间相对顺序。比方说，[2,3,5] 是 [1,2,3,4,5] 的一个子序列而 [1,5,3] 不是。例如：

Example 1：
Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6]
Output: 18
Explanation: Take subsequence [2,-2] from nums1 and subsequence [3,-6] from nums2.
Their dot product is (2*3 + (-2)*(-6)) = 18.

Example 2：
Input: nums1 = [-1,-1], nums2 = [1,1]
Output: -1
Explanation: Take subsequence [-1] from nums1 and subsequence [1] from nums2.
Their dot product is -1.

Constraints:
1 <= nums1.length, nums2.length <= 500
-1000 <= nums1[i], nums2[i] <= 1000

2. 算法思路

Dynamic Programming

这道题和 LeetCode 72. Edit Distance很类似，今天等下去做一下试试。还有GeekForGeeks的这个Find Maximum dot product of two arrays with insertion of 0’s基本一致。

首先根据数据规模，判断复杂度最多只能是O(mn)，不会更多，因此使用DP（做多了应该就一眼看出来了）。

我们设 dp[i][j] 为使用nums1[0 ~ i]和nums2[0 ~ j]的非空子序列的最大点积，那么有如下四种情况。

1. nums1的第i个元素被纳入了最终解中，而nums2的第j个元素没有被纳入最终解中，dp[i][j] = dp[i][j - 1]；
2. nums1的第i个元素没有被纳入了最终解中，而nums2的第j个元素被纳入最终解中，dp[i][j] = dp[i - 1][j]；
3. nums1的第i个元素和nums2的第j个元素都被纳入到最终解的计算中，dp[i][j] = max(dp[i - 1][j - 1], 0) + nums[i] * nums[j]。
4. nums1的第i个元素和nums2的第j个元素都没有被纳入到最终解的计算中，dp[i][j] = dp[i - 1][j - 1]；

但是我们其实会发现，第四种情况根本就是不需要考虑的情况，因为dp[i - 1][j]和dp[i][j - 1]一定是大于等于dp[i - 1][j - 1]的，所以第四种情况我们pass掉，就变成了从三种情况中取最大值。

那么base case是什么样的呢？我们有两种方式进行选择，进行padding或者不进行padding。不进行padding的话可能会多出一些判断条件。padding的意思就是定义一些额外的情况，从而不需要判断边界。

Attention:

这里有几个需要注意的点：

  1. 首先，这里数字有正有负，所以有可能出现前面dp的值都为负数的情况，所以在上面的第三种情况中，如果我们需要nums[i] * nums[j]，则需要判断前面是否小于0，如果小于0，则抛弃前面的dp值。

3. 解法

  1. Dynamic Programming (with padding)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int n1 = nums1.length, n2 = nums2.length;
        int[][] dp = new int[n1 + 1][n2 + 1];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MIN_VALUE);
        }

        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                dp[i][j] = Math.max(Math.max(dp[i][j - 1], dp[i - 1][j]), Math.max(0, dp[i - 1][j - 1]) + nums1[i - 1] * nums2[j - 1];
            }
        }

        return dp[n1][n2];
    }
}

  1. Dynamic Programming (without padding)
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 maxDotProduct(int[] nums1, int[] nums2) {
        int n1 = nums1.length, n2 = nums2.length;
        int[][] dp = new int[n1][n2];

        for (int i = 0; i < n1; i++) {
            for (int j = 0; j < n2; j++) {
                dp[i][j] = nums1[i] * nums2[j];
                if (i > 0 && j > 0) {
                    dp[i][j] = Math.max(dp[i - 1][j - 1], 0) + dp[i][j];
                }
                if (i > 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j]);
                }
                if (j > 0) {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i][j]);
                }
            }
        }

        return dp[n1 - 1][n2 - 1];
    }
}

Prev
2020-05-24 21:30:54 # leetcode # dynamic programming
Next