LeetCode: Max Dot Product of Two Subsequences (Hard)

問題はこちら

leetcode.com

二つの配列 nums1 と nums2 が与えられる。同じ長さの空でない部分列を nums1, nums2 から順序を変えずに選んだ時の内積の最大値を求めよ。

$1 \leq nums1.length, nums2.length \leq 500$
$-1000 \leq nums1 _ {i} , nums2 _ {i} \leq 1000$

考え方

DPの典型問題（解けませんでしたが... ）

LCSと関わりが深いので、こちらの記事でLCSについて勉強しておくと良いかもしれない。

hiramekun.hatenablog.com

全ての部分列を考慮する方法だと、 $\sum _ {i=1} ^ {500} {} _ {500} C _ {i} \times _ {500} C _ {i}$ 程度かかり到底間に合わない。

ここで注目したいのが、nums1[i1] と nums2[i2] を使用した時、次に使用するのはそれぞれ i1, i2 以降のindexになるということだ。つまり、 「index(i1, i2) という状態は、それ以前のindexからしか到達しない」 ということ。

ここまでわかると、DPで解けることがわかる。というのも、題意をみたすように index i1, i2 の状態に来るには、なるべく大きい値を取るようにして遷移してくればよいためだ。

よって、DPの遷移は以下のようになる

dp[i1][i2]: nums1 の $i$ 番目、 nums2 の $j$ 番目までの部分列における内積の最大値。
nums1[i1] と nums2[i2] を使用する時
- 題意では空でない部分列を求めるため、使用する場合は今までの値を使うか、それともこの場所から使用をスタートするかを選ぶことができる。
- dp[i1][i2] = max(dp[i1][i2], max(0, dp[i1 - 1][i2 - 1]) + nums1[i1 - 1] * nums2[i2 - 1]
nums[i1] とnums2[i2] を使用しない時
- それぞれ、一つ隣のindexから遷移し、大きければ採用する。
- dp[i1][i2] = max(dp[i1][i2 - 1], dp[i1][i2])
- dp[i1][i2] = max(dp[i1 - 1][i2], dp[i1][i2])

解答

https://leetcode.com/submissions/detail/343972017/

class Solution {
public:
    int maxDotProduct(vector<int> &nums1, vector<int> &nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, INT_MIN));
        dp[0][0] = 0;
        for (int i1 = 1; i1 <= n1; ++i1) {
            for (int i2 = 1; i2 <= n2; ++i2) {
                dp[i1][i2] = max(dp[i1][i2 - 1], dp[i1][i2]);
                dp[i1][i2] = max(dp[i1 - 1][i2], dp[i1][i2]);
                dp[i1][i2] = max(dp[i1][i2],
                                 max(0, dp[i1 - 1][i2 - 1]) + nums1[i1 - 1] * nums2[i2 - 1]);
            }
        }
        return dp[n1][n2];
    }
};

ひらめの日常

日常のメモをつらつらと

LeetCode: Max Dot Product of Two Subsequences (Hard)

問題はこちら

考え方

解答